#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^{\prime }=max(d_x,d_{x+a_i},d_{x-a_i}+a_i)$$

 

이렇게 해서 최종적인 $d_0$ 값을 보고 0이면 -1을 출력하고 아니면 $d_0$ 값을 출력하면 됩니다.

 

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