(Python/🥇1)백준알고리즘 1450번 : 냅색문제

 

문제 바로가기

문제:

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다. N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

입력:

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

출력:

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

 

풀이:

import bisect
import sys
from itertools import combinations

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, c = map(int, input().split())
arr = list(map(int, sys.stdin.readline().rstrip().split(" ")))
left = arr[:n // 2]
right = arr[n // 2:]

sumleft = []
sumlst2 = []

for i in range(len(left) + 1):
    sumleft += map(sum, combinations(left, i))
for i in range(len(right) + 1):
    sumlst2 += map(sum, combinations(right, i))
sumlst2.sort()
res = 0
for i in sumleft:
    if c - i < 0:
        continue
    res += bisect.bisect_right(sumlst2, c - i)
print(res)

 

이 문제는 

 

물건은 30개 , 고르냐(o), 안고르냐(x) 2^30  1초로는 부족하다

이것을 해결하기 위해 나눠서 풀이하는 방법인데.

Meet In The Middle (MITM) 알고리즘이다

 

만약전발으로 하면 2^15 , 2^15 가 된다.

 

왼쪽과 오른쪽을 나눠 나올수 있는 합을 다 저장해 두고

왼쪽을 포문을 돌려 오른쪽 어디까지 갈 수 있는지 찾으면 된다.