백준 1450 - 냅색문제 (파이썬)

Answer

from sys import stdin

input = stdin.readline

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

aw = weight[:n // 2]
bw = weight[n // 2:]
asum = []
bsum = []

def find(arr, sumarr, i, w):
    if i >= len(arr):
        sumarr.append(w)
        return

    find(arr, sumarr, i + 1, w)
    find(arr, sumarr, i + 1, w + arr[i])

def binary_search(arr, target, start, end):
    while start < end:
        mid = (start + end) // 2
        
        if arr[mid] <= target:
            start = mid + 1
        else:
            end = mid
            
    return end

find(aw, asum, 0, 0)
find(bw, bsum, 0, 0)
bsum.sort()

cnt = 0

for i in asum:
    if c - i < 0:
        continue
    
    cnt += binary_search(bsum, c - i, 0, len(bsum))

print(cnt)