#1126 같은 탑(dynamic programming)

이 문제는 수열이 주어졌을 때, 각각의 수를 왼쪽, 오른쪽, 또는 사용치 않음으로 분류했을 때, 왼쪽 수열의 합과 오른쪽 수열의 합이 같은 경우, 그 값의 최대값이 얼마인가를 묻는 것입니다.

 

예를 들어서, 14 3 20 15 15 14 24 23 15 이란 값이 있다고 하죠.  그러면, 왼쪽에 [14] 오른쪽에 [14]란 수열이 있다면, 그 합이 14로 같기 때문에 같은 합이 될 수 있습니다.  하지만 이것은 최대값은 아닙니다.  [14, 15]와 [14, 15]와 같이 쉽게 찾을 수 있는 값만 해도 29로 더 큰 값이 되기 때문이죠.  [14, 20, 15, 15] 와 [3, 14, 24, 23] 로 나누면 64라는 최대값을 얻습니다.  여기서 중요한 것은 주어진 수열의 한 숫자는 왼쪽, 오른쪽, 또는 사용치않음 세 그룹 중 하나에 속해야 한다는 것이죠.

 

문제는 아래 링크에 있습니다.

 

https://www.acmicpc.net/problem/1126

1126번: 같은 탑

 

이 문제는 동적 계획법을 이용해서 풀게 되는데요.  동적 프로그래밍을 그냥 이용하면 시간초과가 나오게 됩니다.  왼쪽 그룹과 오른쪽 그룹의 차이 x와 참여한 수열의 개수 n 가지고 동적계획법을 아래와 같이 작성하면,

 

\[ d_{n, x} = max( d_{n-1, x}, d_{n-1, x+a_n}, d_{n-1, x-a_n}+a_n ) \]

 

이렇게 해서 \(d_{n, 0}\)  값을 구하면 답이 나오지 않는 것은 아니지만, 시간이 많이 걸립니다.

 

조건을 보고서 어떻게 하면 될 것인지를 판단해야 합니다.  N은 50이므로, 조합해서 나올 수 있는 경우의 수는 무려 \(2^{50} \simeq 10^{15}\)정도니까요.  서로 다른 부분합이 저 경우의 수만큼 나올 수 있겠지만, 이 문제에서는 50개 숫자의 합은 500,000 이하의 자연수라고 합니다.  그러면 경우의 수가 아무리 많아도, 실제 부분합은 500,000 이하라는 이야기죠.  즉, 중간에 부분합들이 중복이 많이 생긴다는 이야기입니다. 

 

위의 식과 비슷하지만, 매번 수열에 \(a_i\) 숫자가 참여할 때마다 새로운 기록을 만드는 방식을 사용했습니다.

 

\[ d'_{x} = max( d_{x}, d_{x+a_i}, d_{x-a_i}+a_i ) \]

 

이렇게 해서 최종적인 \( d_{0} \) 값을 보고 0이면 -1을 출력하고 아니면 \( d_{0} \) 값을 출력하면 됩니다.

 

하지만 이렇게 해도 시간이 좀 많이 걸리게 됩니다.  일단, 최대 250,000개가 생긴다고 할 때, 전체 위의 작업을 계속하게 되면 12,500,000 작업이 이루어지게됩니다.  그래서 저는 내림차순으로 정렬을 하고, 남은 숫자의 합이 두 그룹 사이의 차보다 작은 경우에는 그 차를 늘리지 않게 함으로써 시간 절약을 했습니다.