1208 - 부분집합의 합 2

1182 - 부분집합의 합 에서 시간 제한이 N=20 에서 N=40 으로 확장된 문제이다.

$2^{20}$ 은 약 100만이라 시간이 충분했지만, $2^{40}$ 은 1조에 가깝다.

문제를 아무리 봐도 좋은 생각이 안 나다가, 주변에서 몇가지 힌트를 받고 해결할 수 있었다.

N개의 정수로 이루어진 배열 a에서 모든 부분집합을 살피려면 위에 말한것과 같이 $2^{40}$ 이라 굉장히 힘들다. 하지만 반으로 나눠서 부분 집합을 살핀다면 이 문제를 해결할 수 있다.

배열 a를 반으로 나눈다. 즉, $ a_0, a_1, \dots a_n $ 을 $ a_0, a_1, \dots a_{n/2} $ 와 $ a_{n/2 +1}, \dots a_n $ 으로 나눈다.

그리고 $ a_0, a_1, \dots a_n $ 에서 나올 수 있는 부분 집합의 합을 A 라 하고 나머지 $ a_{n/2 +1}, \dots a_n $ 나올 수 있는 부분 집합의 합을 B 라 하자.

그럼 문제의 정답은 (A의 원소로만 가능한 경우) + (A+B로 가능한 경우) + (B로만 가능한 경우) 로 나타낼 수 있다.
각각의 배열을 만드는 시간은 $2^{20}$ 을 두 번 하면 되고, "A+B로 가능한 경우"는 배열 B에 S-A[i]의 원소가 있는 지를 확인하면 된다.

S=0 이고 a = [ -7, -3, -2, 5, 8 ] 같은 경우는 A = { [-7, -3] 으로 나타낼 수 있는 부분 집합들 } 이고 B = { [-2, 5, 8] 으로 나타낼 수 있는 부분 집합들 } 이다. 이를 자세히 적는다면 A = [ -7, -3, -10 ], B = [ -2, 5, 8, 3, 6, 11 ] 이다.
여기서 답은 (A의 원소로만 가능한 경우 = 0) + (A+B로 가능한 경우는 -3+3=0 으로 1개) + (B로만 가능한 경우 = 0) 으로 1 이다.

주의해야 할 점은, 원소가 같은 것이 여러 개 있을 수 있다. 예를 들어 A = [0, 2, 2], B = [2, 2, 4] 라면 각 숫자는 서로 다르기 때문에 따로 세어야하고 A+B 로 만들어지는 2+2 의 경우들도 모두 서로 다르게 조합된 것들이기 때문에 모두 세어야 한다. 같은 2+2 이지만 $A_1 + B_0$ 은 2 + 2 인 것이고, $A_2 + B_0$ 은 (0+2) + 2 이기 때문이다.