문제

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

풀이

물건의 개수가 $1 <= N <= 30$이고 가방 최대 무게는 $0 <= C <= 10^9$이다. 시간 복잡도가 $O(N \times C)$인 냅색 알고리즘으로는 불가능하다. 그리고 브루트포스로 진행을 할 경우에도 선택 함, 선택 안함으로 2가지의 경우의 수가 있고 물건의 개수가 최대 30개이므로 최대 $2^{30}$번의 연산이 필요하므로 브루트포스로도 불가능하다.

이럴 때 사용하기 좋은 알고리즘으로 Meet in the middle(중간에서 만나기)가 있다. 데이터를 반으로 쪼개 각각 브루트포스를 진행하는 것으로 이 문제의 경우 $2^{15} + 2^{15}$이 되므로 대략 65,000번의 연산으로 처리가 가능하다.

import sys
from itertools import combinations
from bisect import bisect_right

input = sys.stdin.readline

N, C = map(int, input().split())
arr = list(map(int, input().split()))

arr_left = arr[:N // 2]
arr_right = arr[N // 2:]

sum_left = []
sum_right = []

for i in range(len(arr_left) + 1):
    for comb in combinations(arr_left, i):
        sum_left.append(sum(comb))

for i in range(len(arr_right) + 1):
    for comb in combinations(arr_right, i):
        sum_right.append(sum(comb))

sum_left.sort()
answer = 0
for s in sum_right:
    if s > C:
        continue
    answer += bisect_right(sum_left, C - s)

print(answer)

우선 물건의 무게 리스트를 arr_left와 arr_right로 나눈다. 그 후 combinations로 모든 조합의 경우의 수를 구한 뒤 그 합을 각각 sum_left와 sum_right에 저장한다.

sum_left[i] + sum_right[j] <= C라면 가방에 넣을 수 있는 경우이므로 그 모든 케이스를 구해야 한다. 근데 sum_left만 $2^{15}$로 길이가 대략 32,000이 될 것이므로 이를 계속 순차 탐색으로 찾는 건 무리이니 이분 탐색으로 찾아주었다.

이분 탐색을 진행하기 위해 우선 sum_left를 정렬 해 주고, 이미 sum_right의 값이 C를 넘는다면 고려할 필요가 없으니 continue로 넘겨준다. 그리고 sum_left에서 C - s의 값의 인덱스를 찾으면 그 인덱스보다 작은 값들은 모두 sum_left[i] + sum_right[j] <= C를 만족할 것이므로(이미 정렬이 되어있으니) 그걸 answer에 계속 더해주면 된다.

def bisect_right(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

위와 같이 bisect_right를 직접 구현하여 풀 수도 있다.