1450_냅색문제

https://www.acmicpc.net/problem/1450

1450번: 냅색문제

 

 

 

Meet in Middle알고리즘을 이용해보라고 힌트가 주어져 있는 문제이다.

 

위 문제같은 경우, 쉽게 생각하면 주어진 배열중에서 합이 c가 넘지않는 부분배열의 개수를 구하는 문제라고 생각해ㅗㄷ 좋을 것이다.

 

예를들어

 

[ 1, 2, ,3 , 4, 5,6 ]

 

해당 6개의 짐이 있다면 합이 10을 넘지않는 부분집합의 개수를 구하는 문제로 봐도 될 것이다.

 

이런 경우 모든 배열을 한번씩 탐색하면 굉장히 많은 탐색을 해야한다. 시간복잡도로 따지면 n^2형태이다.

 

그렇다면 이렇게 생각해보자

 

해당 배열을 아래와 같이 두개로 만든다

 

[ 1, 2, 3 ]

[4 , 5, 6 ]

 

그리고 배열을 두개 만든후, 각각의 부분집합의 합이 c가 넘지않는 경우의 부분합을 저장한다.

 

[ 1 , 2 ,  3 , 3  ,4  ,5 ]

[ 4 , 5 , 6 ,9 ]

 

해당 과정에서는 조합이 사용될 것이다. 해당 배열을 X,Y라고 생각해보자.

 

그러면 두 배열들의 조합을 합쳐서 c가넘지않는 개수를 세서 더해주면 된다. 해당 개수를 cnt라고 둔다면,

 

a배열의 길이 + b 배열의 길이 + cnt 가 정답이 될 것이다.

 

그런데 이 과정또한 조합을 사용하면 똑같이 시간복잡도가 n^2가 나오는데 이를 이진탐색을 통해서 상당히 줄일 수 있다. 먼저 이분 탐색을 사용하기 위해 두 배열중 하나를 오름차순으로 만들어주고, X배열을 돌면서 정렬된 Y배열과 합이 c가 안되는 경계점을 찾으면, 그전까지는 모두 합쳐서 c가 되지 않는 경우이기에 더해줄 수 있다.

 

 

import sys
from itertools import combinations
n,c = map(int,sys.stdin.readline().split())
lst = list(map(int,sys.stdin.readline().split()))
a,b = lst[:n//2] , lst[n//2:]
A,B = [],[]
cnt = 1
for i in range(1,len(a)+1):
    for j in combinations(a,i):
        SUM = sum(j)
        if SUM <= c:
            A.append(SUM)
for i in range(1,len(b)+1):
    for j in combinations(b, i):
        SUM = sum(j)
        if SUM <= c:
            B.append(SUM)
B.sort()

for i in A:
    start,end = 0 , len(B)
    while start < end:
        mid = (start+end)//2
        if i + B[mid] <= c:
            start = mid+1
        else:
            end = mid   #이분탐색 +1은 start에
    cnt += end   #end값을 더해야함 mid값 x
print(len(A) + len (B) + cnt)