[🥇1 / 백준 1450 / 파이썬] 냅색문제 (MITM)

 

1450번: 냅색문제

 

문제

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다.

출력

첫째 줄에 가방에 넣는 방법의 수를 출력한다.

 

예제 입력  2 1 1 1

예제 출력  3

 

풀이

 

MITM(Meet In The Middle) 알고리즘을 배우는 문제이다.

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

 

이 문제에서 가방에 넣을 수 있는 모든 물건의 조합을 찾는다고 가정해보자.

물건은 총 30개이고 선택, 선택 안 함 2 가지의 경우가 있으니 총 2^30의 경우의 수가 나올 것이다.

이는 약 10억으로, 조합만 구해도 시간초과에 걸릴 것이다.

 

따라서 MITM을 이용해 연산을 줄일 것이다.

물건을 반으로 나눈 뒤 각각의 조합을 구한다.

2^15, 2^15의 경우의 수가 나올 것이다.

반으로 나누었을 뿐인데 조합의 수가 10억에서 32,768 * 2로 줄었다.

조합의 수가 감소했다는 말은 즉 연산의 수가 줄었다는 것이다.

 

이제 이 두  A, B 조합으로 답을 찾을 것이다.

투 포인터 문제이기 때문에 A를 for문으로 돌며 B를 탐색하고자 했다.

B를 정렬한 뒤 끝에서 인덱스를 감소해나가며 두 합의 무게가 조건을 만족할 시,

그 아래 무게의 물건들은 모두 조건을 만족할 것이므로 인덱스를 답에 더하면 될 것이라 생각했다.

 

하지만 시간초과가 발생했다.

MITM을 했지만 결국 O(N^2)의 알고리즘을 한 번 더 사용했기 때문인 것 같다.

그래서 같은 방법이지만 B를 upper bound 이분 탐색을 이용하여 인덱스를 찾았다.

 

결과는 성공.

 

import sys
input = sys.stdin.readline

n,c = map(int,input().split())
w = list(map(int,input().split()))
w1,w2 = w[:n//2],w[n//2:]
wl,wr = [],[]

# 완전 탐색
def bf(arr,seq,idx,summ):
    if len(arr) == idx:
        seq.append(summ)
        return seq
    
    bf(arr,seq,idx+1,summ)
    bf(arr,seq,idx+1,summ+arr[idx])
    
    return seq

# 절반씩 탐색
wl = bf(w1,wl,0,0)
wr = sorted(bf(w2,wr,0,0))
r = 0

for i in wl:
    if c-i < 0:
        continue
    
    # 이분 탐색
    start,end = 0,len(wr)
    while(start < end):
        mid = (start+end)//2
        if wr[mid] <= c-i:
            start = mid+1
        else:
            end = mid
    r+= start
print(r)

 

 

Bisect 모듈을 이용한다면 더욱 간단하게 구현이 가능하다.

일반적으로 시간복잡도도 더 감소할 것이다.

 

import sys,bisect
input = sys.stdin.readline

n,c = map(int,input().split())
w = list(map(int,input().split()))
w1,w2 = w[:n//2],w[n//2:]
wl,wr = [],[]

def bf(arr,seq,idx,summ):
    if len(arr) == idx:
        seq.append(summ)
        return seq
    
    bf(arr,seq,idx+1,summ)
    bf(arr,seq,idx+1,summ+arr[idx])
    
    return seq

wl = bf(w1,wl,0,0)
wr = sorted(bf(w2,wr,0,0))
r = 0

for i in wl:
    if c-i < 0:
        continue
    
    idx = bisect.bisect_right(wr,c-i)
    r+= idx
print(r)