[BOJ] 1208번 : 부분수열의 합 2(중간에서 만나기, 이분 탐색)

접근

세상에나 중간에서 만나기라는 알고리즘이 있다는 것이 신기하다.

부분수열의 합은 고등학생 때 부분집합의 갯수를 구하는 공식을 떠올려보면 이해하기 쉽다.

고등학생 때 전체 집합의 원소의 갯수가 $ N $ 개라면, 부분집합의 갯수는 $ 2^N $이 되었다.

그런 이유는 공집합에 원소마다 [넣기 / 안넣기] 2가지의 선택권밖에 없었기에, $ 2 * 2 * ... * 2 = 2^N $으로 도출될 수 있는 것이다.

여기선 최악의 경우를 생각해보면, $ O(2^{40}) $의 시간복잡도가 나오게 된다.

 

중간에서 만나기는 이분 탐색과 분할 정복의 형태와 비슷하다. 이분 탐색은 매 탐색마다 $ N / 2 $ 를 수행해서 시간 복잡도가 log 단위로 나오는 반면, 중간에서 만나기는 처음 한번 $ N / 2 $ 수행하고, 나눈 두 부분집합을 이용해서, 조건에 맞는 케이스를 구하는 방식이다. 그렇기 때문에 시간복잡도는 $ O(2 * 2^{N/2}) $로 그래도 원래의 시간복잡도의 절반정도로 줄일 수 있는 것이다.

 

중간에서 만나기는 다음과 같은 과정을 따른다.

• 먼저 가운데를 기준으로 전체 집합을 두개의 부분 집합으로 나눈다.
• 한쪽에서 우리가 구해야하는 조건의 일부를 구한다.(이 문제의 경우, 부분수열 합이 나오는 갯수를 구해야 한다.)
• 반대쪽에선 앞서 구한 데이터를 이용해서 우리가 구해야하는 조건의 전체를 구한다.

이 문제에서 예를 들면 부분수열의 합이 10인 부분수열의 갯수를 구한다고 해보자.

그럼 한쪽에서 부분 수열의 합이 2가 나오는 부분수열의 갯수가 10개 있고, 다른쪽에서 부분 수열의 합이 5가 나오는 부분수열의 갯수가 20개가 있다고 해보자.

그럼 10 * 20 = 200가지가 부분수열의 합이 10이 나올 수 있는 부분수열의 전체 갯수가 될 것이다.

 

이 방식으로 문제를 두가지 부분으로 분할하여 해결해보자.

 

해결

만약 전체 수열 $ [-7, -3, -2, 1, 5, 6, 10] $이 있다고 하자.

가운데를 기준으로 왼쪽과 오른쪽으로 수열을 나눠보자.

 

• $ Left : [-7, -3, -2] $
• $ Right : [1, 5, 6, 10] $

왼쪽에서 나올 수 있는 부분 수열의 합들을 구해보면,

$ n = 0 \rightarrow 0 \\ n = 1 \rightarrow -7, -3, -2 \\ n = 2 \rightarrow -10, -9, -5 \\ n = 3 \rightarrow -12$

이렇게 나오게 된다.

 

오른쪽에서 나올 수 있는 부분 수열의 합들을 구해보면,

$ n = 0 \rightarrow 0 \\ n = 1 \rightarrow 1, 5, 6, 10 \\ n = 2 \rightarrow 6, 7, 11, 11, 15, 16 \\ n = 3 \rightarrow 12, 16, 17, 21 \\ n = 4 \rightarrow 22 $

이렇게 나오게 된다.

 

그렇다면 각각 나온 합들을 갯수로 표현해보자.

 

Left

 

$ -12 : 1 \\ -10 : 1 \\ -9 : 1 \\ -7 : 1 \\ -5 : 1 \\ -3 : 1 \\ -2 : 1 \\ 0 : 1 $

 

Right

 

$ 0 : 1 \\ 1 : 1 \\ 5 : 1 \\ 6 : 2 \\ 7 : 1 \\ 10 : 1 \\ 11 : 2 \\ 12: 1 \\ 15 : 1 \\ 16 : 2 \\ 17 : 1 \\ 21 : 1 $

 

만약 우리가 구하고자 하는 부분 수열의 합이 16이라고 해보자. 그렇다면 양쪽에서 뽑을 수 있는 부분 수열의 합 케이스는

$ (Left, Right) = (-5, 21), (0, 16) $

이렇게 될 것이다.

그러면 $ (-5, 21) $의 케이스는 $ 1 * 1 = 1 $개가 될거고, $ (0, 16) $의 케이스는 $ 1 * 2 = 2 $개가 될 것이다.

그렇기 때문의 총 갯수는 3개가 된다.

 

이런식으로 문제는 해결하면 된다.

 

Left, Right의 연산 결과를 따로 저장해서 나중에 곱하는 방법도 있지만, 연산 결과를 한번만 저장해서 효율적으로 해결할 수 있으니 그건 코드를 참조해서보자. 하지만 이 방법은 부분 수열이 공집합이 되는 케이스가 2번 들어가기 때문에 정답이 0이 되는 케이스를 주의해서 표시해주자.

코드

from collections import defaultdict

N, S = map(int, input().split())
nums = list(map(int, input().split()))

cnt = 0
summ_dict = defaultdict(int)

def right_search(mid, partial_sum):
    if mid == N:
        summ_dict[partial_sum] += 1
        return
        
    right_search(mid+1, partial_sum)
    right_search(mid+1, partial_sum + nums[mid])
    
def left_search(st, partial_sum):
    global cnt
    if st == N//2:
        if summ_dict[S - partial_sum]:
            cnt += summ_dict[S - partial_sum]
        return
        
    left_search(st+1, partial_sum)
    left_search(st+1, partial_sum + nums[st])
    
right_search(N//2, 0)
left_search(0, 0)

print(cnt if S else cnt-1)