trytur   1년 전

조합을 구현하지 않아도 코드가 정상 통과됩니다.(22~30번째 줄 참고)

조합을 구현하지 않는다면, 난쟁이 1명의 키를 2번 뺐을 때 100인 경우가 생긴다면,

출력값은 9개가 됩니다. 또한, 문제의 조건을 만족하지도 않습니다.

kimhs   1년 전

정렬한 뒤의 키를 각각 A1 ~ A9로, A1~A9의 합을 S로 나타내겠습니다. 

항상 일곱 난쟁이를 찾을 수 있다는 문제의 조건에 따라, S - (Ai + Aj) = 100 이고 i ≠ j인 순서쌍 (i, j)가 적어도 하나 존재합니다. 

만약 S - 2 * Ak = 100인 Ak가 존재한다면, Ai + Aj = 2 * Ak이므로, Ai < Ak < Aj 혹은 Aj < Ak < Ai 를 만족합니다. (따라서 i < k < j 혹은 j < k < i 입니다)

작성하신 코드는 I가 가장 큰 순서쌍을 찾습니다. 따라서 마지막에 절대로 I에 Ak의 인덱스가 저장될 수 없으며, 항상 올바른 답을 찾아냅니다.

trytur   1년 전

감사합니다!!!

댓글을 작성하려면 로그인해야 합니다.