[Python 3] BOJ - 1208 "부분수열의 합 2"

 # 문제 링크 : https://www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

 # 풀이 :

개인적으로 이 문제는 부분수열의 합1의 이분탐색 버전이라고 생각한다. 길이가 N인 수열의 부분수열의 전체 경우의 수는 2의 N승인데, 문제에서 N이 40이므로 2 ^ 40 = 1,099,511,627,776이므로 시간초과를 피할 수 없다. 따라서 수열을 반으로 나눈다면 2 ^ 20 = 1,048,576이므로 부분집합을 크게 두 부분으로 구할 수 있다. 따라서, 두 부분을 탐색하면서 각각의 합이 S면 순서쌍을 세어주면 정답을 구할 수 있다

<그림 1. 부분집합 이분 분할>

 현재 수열이 {-7,-3,-2,5,8}인 상황이라고 가정하자. 이 경우는 크기가 작아 32번만에 모든 부분집합을 구할 수는 있지만 위 단락에서 본 바와 같이 두부분으로 나누어서 구해보겠다. 따라서, 좌측의 Subset중 하나를 고르고, 우측의 Subset중 하나를 고르면 모든 부분집합에 대해 표현이 가능하다. 즉, 분할하여 구할 수 없는 {-7,-3,-2,5}의 경우, 좌측의 {-7,-3,-2}를 고르고 우측의 {5}를 고르면 충분히 표현이 가능하다.

<그림 2. 좌,우측의 Subset의 합>

 그러나 우리는 부분집합의 합이 S가 되는 경우를 구해야 하므로 좌측의 각각의 Subset의 합을 left에, 우측의 각각의 Subset의 합을 right에 저장하면 위 그림2와 같이 됨을 알 수 있다. 이 때 S는 0이라고 가정하자. 이 때 left와 right에 대한 포인터를 각각 f,r이라고 하자. 현재의 경우 left[f] + right[r]의 경우는 1로서 0보다 크다. 그렇다면 두가지 경우가 존재한다.

 f를 이동하는 것과 r을 이동하는 것인데, 현재 left는 오름차순으로 정렬되어 있고, right는 내림차순으로 정렬되어 있다. 따라서, r을 이동시켜야 한다. 같은 논리로 left[f] + right[r]이 S보다 작다면 f를 이동시켜야 한다. 만일 S라면 f와 r 모두 이동시켜야 한다.

 따라서 위 그림 2에서는 f가 4, r이 2일 때와 f가 7, r이 3일 때 left[f] + right[r] = 0이므로 가능한 순서쌍은 2개라고 할 수 있다. 그런데, 문제의 조건에서 부분집합이 공집합은 경우를 제외한다고 했으므로 S가 0인 경우는 left, right가 모두 공집합인 경우를 빼줘야 한다. 

<그림 3. 합이 같을 때 예외 경우>

 위 그림 3에서 left[f1] + right[r1]이 S이므로 한가지 쌍이 추가된다. 위 단락의 움직이는 경우에 따라 S와 같으므로 f1과 r1은 각각 한칸씩 움직여 f2,r2가 된다. 그런데 만일 여기서 바로 left[f2] + right[r2]를 비교하게 되면, (f1, r2), (f1, r3)의 경우를 놓치게 되므로 left와 right 모두 한칸 움직였을 때도 움직이기 전과 같은 수라면 쌍을 추가할 수 있기 때문에 더이상 같은 수가 나오지 않을 때 까지 갯수를 세어주고 각각의 값을 곱하면 합은 같지만 구성이 다른 순서쌍을 모두 구할 수 있다. 현재 left에서는 -5와 같은 수가 자기자신밖에 없으므로 1이고, right에서 5와 같은수가 3개 있으므로 1 * 3 = 3개의 순서쌍이 올바르게 구해짐을 알 수 있다.

 

 # 코드

import sys

# 입력부
n,s = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))

# 이분 분할
m = n//2
n = n - m

# first : 왼쪽 Subset
first = [0] * (1<<n)

# 비트마스킹을 이용하여 Subset의 합을 담는다
for i in range(1<<n):
    for k in range(n):
        if (i&(1<<k)) > 0:
            first[i] += a[k]
            
# second : 오른쪽 Subset
second = [0]*(1<<m)
for i in range(1<<m):
    for k in range(m):
        if (i&(1<<k)) > 0:
            second[i] += a[k+n]
            
# first 오름차순 정렬, second 내림차순 정렬
first.sort()
second.sort(reverse = True)

# n, m = first의 길이, second의 길이
n = (1<<n)
m = (1<<m)
i = 0
j = 0
ans = 0
while i < n and j < m:

    # 같은 경우
    if first[i] + second[j] == s:
        # i,j를 이동
        c1 = 1
        c2 = 1
        i += 1
        j += 1
        # 예외 처리
        while i < n and first[i] == first[i-1]:
            c1 += 1
            i += 1
        while j < m and second[j] == second[j-1]:
            c2 += 1
            j += 1
        # 전체 순서쌍 반영
        ans += c1*c2
        
    # 큰 경우 i만 이동
    elif first[i] + second[j] < s:
        i += 1
        
    # 작은 경우 j만 이동
    else:
        j += 1
        
# s가 0인 경우 공집합의 경우를 빼줘야 하므로 1감소
if s == 0:
    ans -= 1
    
# 정답 출력
print(ans)