작심 큰일 챌린지 - 냅색 문제 (파이썬)

새로 배운 개념이나 기술:

Meet in the Middle은 브루트포스 탐색 범위를 절반으로 나누어 시간 복잡도를 획기적으로 줄이는 알고리즘 기법으로, O(2^N) 수준의 문제를 O(2^(N/2)) 시간으로 해결할 수 있게 해준다.

이 문제에서는 N이 30으로, 가능한 모든 부분집합의 수가 최대 2³⁰ (약 10억)에 달하므로 단순 브루트포스로는 시간 초과가 발생한다. 따라서 N개의 물건을 두 그룹으로 나눈 뒤 각각의 부분집합 합을 구해 Meet in the Middle 방식으로 해결해야 한다.

또한, A 그룹의 부분합에 대해 B 그룹의 부분합을 하나씩 순회하며 a + b ≤ C 조건을 확인하면 시간 복잡도가 O(2¹⁵ × 2¹⁵) = O(2³⁰)이 되어 비효율적이다. 이를 개선하기 위해 B 그룹의 부분합을 미리 정렬한 뒤, A 그룹의 각 부분합에 대해 이분 탐색을 적용하면 O(log 2¹⁵) = O(N) 시간 안에 조건을 만족하는 B 그룹의 원소 수를 구할 수 있다.

결과적으로 전체 시간 복잡도는 O(2^(N/2) × log(2^(N/2))) = O(N × 2^(N/2))로 줄어들며, 이는 N이 30 이하일 때 충분히 해결 가능한 수준이다.

어려웠던 점과 해결 방법:
"N개의 물건을 가방에 넣는 방법의 수" =
"N개의 물건들 중 아무거나 골라서 (부분집합), 그 합이 C 이하인 경우의 수"

 

import sys
input = sys.stdin.readline
from itertools import combinations
from bisect import bisect_right
def solution():
    n, c = map(int, input().split()) # n개의 물건, 가방에 최대 c만큼의 무게를 넣을 수 있다.
    weights = list(map(int, input().split()))
    # 2**30 -> 약 10**9(10억)로 시간초과가 나기 때문에 반으로 나누기
    a = weights[:n//2]
    b = weights[n//2:] # n이 홀수라면 len(a) < len(b)
    # a, b그룹의 부분집합의 합을 모두 구하기
    suma = []
    sumb = []
    # i개수만큼 골라서 부분집합 만들기
    for i in range(len(a)+1): # 0개(공집합) ~ len(a)개(전체) 고를 수 있다.
        for j in combinations(a, i):
            suma.append(sum(j))
    for i in range(len(b)+1):
        for j in combinations(b, i):
            sumb.append(sum(j))

    count = 0
    # suma 원소들 + sumb 원소들 <= c 인 가지 수 구하기
    sumb.sort() # 이진탐색을 위해 정렬하기
    for sa in suma:
        target = c-sa
        count += bisect_right(sumb, target)
    print(count)
solution()