[Python] 백준 - 1450 냅색문제

 

문제

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

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

입력

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

출력

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

 

문제해결방법- (구글링 참조)

 

 

1. 처음에는 문제가 이해가 안되었다. 안 넣는 것도 방법의 수에 포함이 되는 모양.

2. Meet in the middle 알고리즘 

 

 

Meet in the middle 이란?

 

 

한번에 연산하기 어려운 문제를 둘로 나누어 시간적인 단축을 꾀하는 알고리즘

 

 

1) 분할없이 경우의 수를 카운트한다면 $2^{n}$ 의 시간복잡도를 갖는다. 최대 $2^{30}$이다.

2) 분할하여 카운트하면 $2^{15}$ , $2^{15}$ 의 연산만을 하게되어 시간복잡도가 현저히 줄어든다고 한다.

 

--> 가방에 c만큼의 무게를 넣을 수 있다면 'left로 분할한 경우의 수에 해당하는 물건들의 합'을 구한 후, 'c와 각 차이'만큼 'right에 담겨있는 경우의 수에 해당하는 물건들의 합'을 담을 수 있을 것이다.

 

 

 

3. 이분탐색 알고리즘

 

1) 여기에서 이분탐색 알고리즘이 활용되는데, 이분탐색은 딱 정해진 target을 찾는 정석적인 알고리즘 외에도, 우측탐색, 좌측탐색의 방법으로 같은 원소 여러 개가 target일 경우, 가장 좌측이거나 가장 우측을 구할 수도 있다.

 

혹은 백준 1654 - 랜선자르기 나, 백준 2805 - 나무자르기 문제처럼 최댓값, 최솟값을 찾는 응용을 할 수도 있다.

 

-> mid 인덱스에 해당하는 값이 같을 때, l을 mid+1 로 하느냐, r을 mid-1 로 하느냐에 따라 우측탐색, 좌측탐색이 된다.

 

-> 해당 코드를 출력을 다 찍어보면 이해가 빠른데, 우측 탐색이라면 해당값을 찾았을 때, l = mid+1로 이동시키고, 이 l은 같은 값이 없다면 고정되고, r만 바뀌게 되어 l > r 이 되는 순간 while문이 종료된다. 이 경우라면 r은 l이 mid+1로 고정되는 순간의 mid를 가리키고 있다. (같은 값이 존재한다면, 가장 우측의 같은 값 + 1 로 l이 고정됨.)

 

-> 하지만 이 문제에서는 c - left의 각 값 보다 같거나 작은 right의 갯수를 구해서 전부 더해주는 것이기 때문에, 이분 탐색의 출력은 r+1 혹은 고정된 l이 되어야 한다. 왜냐하면 (ㅇ, ㅇ, 3, 3, r , l , ㅇ ...) 일 경우 갯수는 mid 인덱스인 4가 아니라 5이기 때문.

 

 

 

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
d = list(map(int, input().split()))

left = d[:n//2]
right = d[n//2:]
l_box, r_box = [], []

def sol(arr, res, idx, temp):
	if idx == len(arr):
		res.append(temp)
		return
	sol(arr, res, idx+1, temp)
	sol(arr, res, idx+1, temp+arr[idx])
	return res

def binary(arr, target):
	l, r = 0, len(arr)-1
	while True:
		if l > r:
			break
		mid = (l+r)//2
		if arr[mid] < target:
			l = mid+1
		elif arr[mid] == target:
			l = mid+1
		else:
			r = mid-1
	return l

sol(left, l_box, 0, 0)
sol(right, r_box, 0, 0)
r_box.sort()
cnt = 0

for i in l_box:
	if c-i >= 0:
		cnt += binary(r_box, c-i)
print(cnt)