[백준] 1208: 부분수열의 합2 - meet in the middle

문제이해

정수로 이루어진 수열 num과 s가 주어지면, num안의 원소중 더한 값이 s가 되도록 하는 경우의 수를 구하는 문제이다. 

계획

먼저 브루스포트로 푸는 경우의 시간복잡도는 2^40으로 1초이내 푸는 것이 불가능하다. 따라서, 시간복잡도를 O(2^N)인 알고리즘을 O(2^(N/2))로 줄일 수 있는 Meet In The Middle 알고리즘을 활용하면 해결할 수 있다.

MITM(Meet In The Middle)

MITM은 N이 그렇게 크지 않지만 완전 탐색을 진행하기엔 무리가 있다고 판단할 때 주로 사용하는 알고리즘이다.

배열을 완전탐색 한다면 O(2^N)시간복잡도가 나올 걸, 배열을 반으로 나눈 뒤 각각의 조합을 구해 O(2^(N/2)+2^(N/2))=O(2^(N/2)) 경우의 수가 나오게 하는 것이 목표이다.

두 배열을 for문으로  돌려 두 조합을 합쳤을 경우까지 생각해도 O(2^N/2)시간복잡도로 비교할 수 있다. 하는 방법은 다음과 같다.

1. num = [1, 2, 3, 4, 5] 배열과 s=7이 주어졌다고 해보자. (n=5, s=7)

2. num을 left와 right로 절반씩 쪼개 저장한다.

left = [1, 2, 3]
right = [4, 5]

3. left와 right 각각의 조합들의 합을 담은 배열 sum_left, sum_right를 구한다.

left = [1, 2, 3]
right = [4, 5]
sum_left = [0, 1, 2, 3, 1+2, 1+3, 2+3, 1+2+3] = [0, 1, 2, 3, 3, 4, 5, 6]
sum_right = [0, 4, 5, 4+5] = [0, 4, 5, 9]

 

O(2^(N/2))로 줄어들었다.

4. sum_left와 sum_right를 비교하며 두 원소를 합했을때 s와 같은 경우를 구해주면 된다.

5. 다음과 같은 방식을 사용해서 비교하면, 시간복잡도를 줄일 수 있다. 

sum_left는 오름차순으로, sum_right는 내림차순으로 정렬을 해준다.

sum_left.sort()
sum_right.sort(reverse=True)

sum_left == [0, 1, 2, 3, 3, 4, 5, 6]
sum_right == [9, 5, 4, 0]

 

따라서 li와 ri를 1씩 증가시켜 주면서 비교를 해주면된다.

0+9 > 7    ->    li = 0, ri = 0
0+5 < 7    ->    li = 0, ri = 1
1+5 < 7    ->    li = 1, ri = 1
2+5 = 7    ->    li = 2, ri = 1
3+5 > 7    ->    li = 3, ri = 1
3+4 = 7    ->    li = 3, ri = 2
3+4 = 7    ->    li = 4, ri = 2
4+4 > 7    ->    li = 5, ri = 2

그 이후는 없다.

같은 경우에 대해서는 예외처리를 해줘야 하는데

sum_left = ... -1 ...

sum_right = ... 8 8 ...

만약 같을 때마다 li += 1, ri += 1을 해버린다면 (-1, 8)을 한 가지로 퉁쳐버린다. 따라서 sum_left에서 같은 수만큼 과 sum_right에서 같은 수 만큼 곱해준 값을 더해줘야 한다.

ans += 1*2

계획수행

import sys

n, s = map(int, sys.stdin.readline().split())
num = list(map(int, sys.stdin.readline().split()))

left, right = num[:n//2], num[n//2:]
sum_left, sum_right = [0]*(1<<len(left)), [0]*(1<<len(right))

for i in range(1<<len(left)):
    for ii in range(len(left)):
        if i&(1<<ii):
            sum_left[i] += left[ii]

for i in range(1<<len(right)):
    for ii in range(len(right)):
        if i&(1<<ii):
            sum_right[i] += right[ii]
#모든 조합의 합을 구해준다.

sum_left.sort()
sum_right.sort(reverse=True)
#sum_left는 오름차순으로, sum_right는 내림차순으로 정렬해준다.

li, ri = 0, 0
ans = 0
lenl, lenr = len(sum_left), len(sum_right)

while li < lenl and ri < lenr:
    if sum_left[li] + sum_right[ri] > s:
        ri += 1		#만약 크다면 ri += 1을 해준다.
    elif sum_left[li] + sum_right[ri] == s:
        c1 = 1
        c2 = 1
        li += 1
        ri += 1
        while li < lenl and sum_left[li-1] == sum_left[li]:
            li += 1
            c1 += 1
        while ri < lenr and sum_right[ri-1] == sum_right[ri]:
            ri += 1
            c2 += 1
        #같은 경우에 대한 예외처리이다.
        ans += c1*c2
    else:
        li += 1		#만약 작다면 li += 1을 해준다.

if s == 0:
    print(ans-1)	#0이라면 sum_left와 sum_right에서 공집합인 경우가 두개가 중복되므로
    				#하나를 빼줘야한다.
else:
    print(ans)

 

느낀 점

아예 개념자체가 새로워서 벽이 느껴졌었다. 중간에 실수라도 하면 답이 없을 것 같다. 적당히 큰데 완전 탐색을 하기에는 무리일 때 meet in the middle 알고리즘을 사용해야겠다.