[24261] Same Sum Subsequences

마지막 수정 시각: 2022-08-31 11:46:15

문제 링크

오랜만에 굉장히 재밌게 풀었던 문제여서 풀이를 정리해봤다.

문제 요약

길이가 \(N\)인 수열 \(A\)와 길이가 \(M\)인 수열 \(B\)가 주어진다. 수열 \(A\)의 모든 원소는 \(1\)이상 \(M\)이하의 정수이고, \(B\)의 모든 원소는 \(1\)이상 \(N\)이하의 정수이다.

\(A\)의 부분 수열의 합 == \(B\)의 부분 수열의 합이 되는 경우를 아무거나 하나 찾아서 출력(물론 각 부분 수열의 길이는 \(1\)이상)

풀이

내가 문제를 풀면서 했던 생각을 순서대로 정리해보았다.

엄청 단순한 세팅의 문제. 근데 Subset Sum 자체가 NP문제여서 단순한 방법으로는 풀 수가 없고, 문제에서 주어진 특수한 조건을 잘 이용해야 한다는 생각이 든다.

일단 문제에서 눈에 띄는 가장 특이한 조건은, \(A\)의 각 원소는 \(1\)이상 \(M\)이하, \(B\)의 각 원소는 \(1\)이상 \(N\)이하라는 양쪽 길이에 비례한 크기 제한이 걸려있다는 점이다. 그래서 이런 크기 특성을 뭔가 이용할 순 없을까 하는 생각이 든다.

또 다른 특징으로는, 양쪽 수열에 동일한 원소가 하나라도 있으면 답은 바로 그 원소가 된다는 것. 따라서 일단 양쪽 수열에 중복된 원소가 없다고 생각하고 풀 수 있다.

접근 1

제일 간단하게 생각나는 방법인 냅색부터 고민해보았다. \(A\)의 원소는 전부 양수, \(B\)의 원소는 전부 음수라고 치면 결국 합이 0이 되는 부분 수열을 찾는 걸로 생각할 수 있으니까. 하지만 이렇게 할 경우 복잡도가 너무 커서 풀 수가 없다... 냅색으로 접근하되 뭔가 크기 제한이 걸려 있는 걸로부터 얻어낼 수 있는 성질이 없을까? 하는 생각이 들었다. 합이 \(NM\)에 비례한다는 점부터가 너무 큰데 이걸 일단 줄여볼 수는 없을까 싶은 생각.

그래서, 처음 든 생각은 대충 \(0\)을 만드는게 목표니까 \(0\)에 가까운 범위에서만 검사하는걸로 충분하지 않을까 하는 것. 어쨌든 각 원소가 \(1\)부터 \(N\) 혹은 \(M\)까지 범위에 있으니 대충 위아래 방향으로 \(max(N,M)\) 정도 범위만 검사해주면 어떨까? 싶은 생각이 들었다. 이렇게 줄여도 \(O(NM)\)이라 시간 안에 안 돌지만.. 그래도 조금은 최적화가 될테니까.

하지만 여기서 생각을 해봐도 어쨌든 냅색으로 접근하면 무조건 (합 크기) * (원소 개수) 만큼의 시간이 걸릴테니 이런 방향으로는 어려울 것 같다는 생각이 들었다. 결국 어떤 증명을 통해 그리디한 방법을 써야 하지 않을까? 싶어서 생각의 방향을 조금 틀었다.

접근 2

그리디하게 접근한다면, 아마도 원소를 하나씩 하나씩 매 순간마다 최선의 규칙에 따라 바로바로 고르고 \(O(N+M)\) 시간 만에 끝을 낼 수 있는 방향일 것이다. 이런 생각과 위 아래로 \(0\) 근처의 범위만 본다는 아까 전의 관찰을 합쳐서, 흔히 보는 투 포인터 유형의 문제를 풀 듯이 일단 접근해보면 어떨까 싶은 생각이 들었다.

즉, 매 순간마다 최대한 합이 \(0\)에 가까워지게 원소를 고르는 것. 지금까지 고른 합이 \(0\)보다 크면 \(B\)의 원소를 고르고, 작으면 \(A\)의 원소를 고른다. 이걸 반복하는 과정에서 합이 정확히 \(0\)이 되면 그 시점까지 고른 원소들이 답이 될 것이다.

이제 이 논리에서, 순서대로 골랐을 때 합이 \(0\)이 안 되는 경우에 어떻게 할 지가 문제가 된다.

여기서 다시 돌아가서 생각해보면, 합이 음수면 \(A\), 양수면 \(B\)의 원소를 고르기 때문에 고른 원소들의 합은 항상 \(-N\) 이상 \(M\) 이하가 된다. 즉, 가능한 합의 경우의 수는 \(N+M+1\)가지. 여기에 합이 \(0\) 인 경우는 바로 답을 구하고 넘어가니까 답이 안 되는 케이스는 \(N+M\)가지 밖에 존재하지 않는다.

여기서 좀 더 생각을 나아가보자. 맨 처음에 골라서 넣어놓는 원소 하나가 \(A\)에 속하는 원소였다고 치면, 중간 단계에서는 정확히 \(0\)을 거칠 수 없으므로 음수 방향으로는 \(-N\)까지 갈 수가 없다. \(-N\)이 되려면 합이 \(0\)인 상태에서 \(N\)을 빼야하는데, 중간 단계에 합이 \(0\)이 나왔다면 거기서 종료되므로 합이 \(-N\)까지 내려갈 수는 없는 것이다. 따라서, 가능한 합의 종류는 \(N+M-1\)가지가 되는데, 실제로 선택을 하는 중간 과정에서 만들어지는 합의 종류는 \(N+M\)가지 이므로 항상 개수가 하나 더 많다. 그렇다면 비둘기집의 원리에 의해 같은 합을 가지는 중간 단계가 반드시 하나가 존재하고, 이 둘을 골라서 빼주면 정확히 합이 \(0\)이 되는 경우가 생긴다.

여기까지 생각하고 답이 맞다고 생각했지만... 생각해보니 항상 \(N+M\)개의 모든 원소를 고를 수 있는게 아니었다. 어느 한 쪽의 합이 훨씬 작아서 한쪽을 다 고르고 나머지 한 쪽 집합의 원소만 애매하게 남는 경우가 발생하고, 이런 경우에는 위의 논리를 적용할 수 없었다.

하지만 이 관찰은 굉장히 유의미하다고 생각했고, 방향성 자체는 맞을 거라는 생각이 들었다. 그래서 여기서 좀 더 고민을 해봤는데.. 어느 한 쪽 원소를 다 쓴 상태에서 해당 수열의 값을 더 뽑아야하는 상황에 도달했다고 생각해보자. 이게 \(A\) 수열이라고 생각하면, 이미 \(N\)번 \(A\) 수열의 원소를 고르는 상황이 발생했다는 뜻이다. 그 말은, 곧 지금까지 고른 원소의 합이 음수인 케이스가 \(N\)번 존재했다는 뜻이기도 하다. 그런 경우가 \(N\)번 있었어야 \(N\)개의 원소를 전부 다 쓰게 되니까. 이 때, 위에서 이야기한 거처럼 고른 원소의 합이 음수가 되기 위해서는 \(0\)이 아닌 상태에서 음수로 내려와야하고, 따라서 만들어질 수 있는 원소의 합이 음수인 케이스는 \(N-1\)가지만 존재한다. 따라서 똑같은 논리로 비둘기 집의 원리에 의해 합이 같은 케이스가 반드시 한 번은 발생하게 된다. 이 논리는 \(B\) 수열이 텅 비어있을 때도 동일하게 적용되므로, 결국 \(O(N+M)\) 시간에 해당 문제를 풀 수 있음을 알 수 있다.