doodle0   1년 전

아래 코드는 AC가 뜨긴 합니다만, 증명을 아무리 생각해도 모르겠습니다.

MITM을 이용한 풀이를 인터넷에 검색해 보면, 대부분 $j\ne k$이면 $a_i+a_j\ne a_i+a_k$이기 때문에 합이 $w$인 인덱스의 쌍이 여러 개가 있어도 그 중 하나만 저장하고 있어도 된다고 하는데, (줄 16~21) 왜 이렇게 가능한 것인지 이해가 가지 않습니다.

왜냐하면 답이 $w=a_x+a_y+a_z+a_t$라고 할 때, 줄 25~31의 (i, j)=(x, y)인 상황에서 sums[az+at]에 (s, x)와 같은 인덱스 쌍이 저장되어 있다면 인덱스가 겹쳐 찾아지지 않을 것이고, 가능한 모든 (i,j)=(x, y), (x, z), ..., (z, t) 쌍에서 똑같은 상황이 벌어진다면 $a_x+a_y+a_z+a_t=w$를 만족하는 쌍이 찾아지지 않을 것 같기 때문입니다.

이런 상황이 만들어지는 예시로서 다음과 같은 입력을 생각해 봤습니다.

41111 10
10001 10010 10100 11000 9911 10091 10991 10109 11009 11099

$(a_x, a_y, a_z, a_t)=(10001, 10010, 10100, 11000)$로 놓으면, $w=a_x+a_y+a_z+a_t$이지만, 가능한 (i,j)=(x, y), (x, z), ... 쌍에 대응되는 인덱스 쌍이 항상 (s, x)와 같이 (i, j)와 중복되는 꼴로 저장됩니다.

11099가 위의 s와 같은 경우입니다. (i, j)=(x, y)일 때 $a_z+a_t=10100+11000=10001+11099=a_x+a_s$입니다. 그래서 $w=a_x+a_y+a_z+a_t$를 찾아내지 못할 것이라고 생각했습니다.

그러나 이러한 경우 마법처럼 $w=a_x+a_y+a_z+a_t$ 대신 $w=10001+10010+10991+10109$을 만족해 YES를 출력하게 됩니다. 이렇게 뜻밖의(?) 해가 항상 존재한다는 것이 보장되는 것일까요?

제가 생각한 것은 여기까지입니다. 글을 잘 정리하지 못했는데, 도움을 얻고 싶습니다. 제가 어떤 점을 간과하고 있는 것일까요?

shoo040113   1년 전

w = x + y + z + t (x < y < z < t)를 만족하는 정답 x, y, z, t가 존재한다고 가정합시다. 질문자님의 코드가 이 정답을 찾아내지 못하는 경우라면 아래와 같은 사실을 만족합니다.

x, y, z, t 중 임의의 수 2개(편의상 a, b)를 골랐을 때, sum[w - a - b]에 적힌 두 수 중에는 a 혹은 b가 존재한다.

이제, 2가지 경우를 살펴봅시다. 

먼저 x와 y를 고르는 경우입니다. 이 경우에 sum[w - x - y]에 적힌 수 중 하나는 x 혹은 y입니다. 그런데 두 수의 합은 z + t여야 하고, x와 y는 모두 z보다 작으므로 나머지 한 수는 t보다 커야 합니다.

z와 t를 고른 경우에도 마찬가지로 생각해 보면 sum[w - z - t]에 적힌 수 중 하나는 z 혹은 t이고, 나머지 하나는 x보다 작은 수일 것입니다.

그런데 이 관찰대로라면 sum[w - x - y]와 sum[w - z - t]에 적힌 수들은 겹칠 수 없습니다. 또, 그 합은 (w - x - y) + (w - z - t) = (z + t) + (x + y) = w로 문제의 조건을 만족합니다.

이 네 수는 위의 "질문자님의 코드가 정답을 찾아내지 못할 조건"을 만족하지 못하므로 이 경우에도 질문자님의 코드는 무조건 다른 정답을 찾아낼 수 있습니다.

doju   1년 전

sums[s]에는 $a_i+a_j=s$를 만족하는 가장 큰(무게 나열에서 가장 오른쪽에 있는) 순서쌍 $(i, j)$가 저장됩니다.

doodle0   1년 전

와... 멋진 답변 감사합니다. 정말 오랫동안 고민하고 있었는데 한방에 시원하게 해결됐습니다!

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