백준 1450번 냅색문제

문제 풀이

• 입력 수열을 2개로 나눈 뒤 각각의 부분집합의 합을 모두 구해주고, 두 부분집합의 합의 원소를 각각 조회하면서 더했을 때 C가 되는 개수를 세면 됩니다.

• weight 리스트를 반으로 나눕니다. 보통 len(weight) // 2 를 기준으로 나누게 되고 이를 aw, bw 라고 부르겠습니다.

• aw, bw 각각을 브루트포스 방법으로 부분 집합의 합을 구해주고 이를 a_sum, b_sum 에 모두 추가해줍니다(총 2^n개, 이진 트리를 조회하는 것처럼 반을 나누면서 들어가 모든 부분 집합의 합을 구합니다).

• b_sum 을 이분 탐색 하기 위해 오름차순으로 정렬해줍니다.

• a_sum 의 원소 i에 대하여 c - i(target) 값보다 작거나 같은 수 중 가장 큰 값을 정렬된 b_sum에서 찾아줍니다(이분 탐색). 여기서 찾아진 수보다 작은 수들은 모두 c보다 작아 가방에 넣을 수 있기 때문에 찾아진 수보다 작은 b_sum 값들 개수만큼 카운트(b_sum의 인덱스)해줍니다.

코드 풀이

import sys

n, c = map(int, sys.stdin.readline().split())
weight = list(map(int, sys.stdin.readline().split()))
aw = weight[:n // 2]
bw = weight[n // 2:]
asum = []
bsum = []


# 모든 부분집합의 합을 구해줍니다.
# sumarr에 쌓이는 총 개수는 2^n 개입니다.
def bruteforce(warr, sumarr, l, w):
    if l >= len(warr):
        sumarr.append(w)
        return

    bruteforce(warr, sumarr, l + 1, w)
    bruteforce(warr, sumarr, l + 1, w + warr[l])


# c - i를 만족하는 인덱스를 b_sum에서 찾습니다.
# 수가 같다면 가장 오른쪽 인덱스를 찾습니다.
# 이분 탐색으로 찾은 인덱스가 뜻하는 것은 c - i 를 만족하는 값
def binarysearch(arr, target, start, end):
    while start < end:
        mid = (start + end) // 2
        if arr[mid] <= target:
            start = mid + 1
        else:
            end = mid

    # print(end)
    return end


# aw와 bw에 대한 asum, bsum를 구합니다.
bruteforce(aw, asum, 0, 0)
bruteforce(bw, bsum, 0, 0)
bsum.sort()   # 이분 탐색을 위해 bsum을 오름차순 정렬

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

아래 포스팅이 이해하는데 많은 도움이 되었습니다.

• https://ca.ramel.be/100