[백준] 1450 - 냅색문제

🖥️ 시작하며

Meet-in-the-Middle 알고리즘: 물건을 두 그룹으로 나누어 각 그룹의 모든 부분집합의 합을 계산합니다. 이는 시간 복잡도를 O(2^N)에서 O(2^(N/2))로 줄입니다.

부분집합 생성 최적화: generate_subsets 함수는 비트마스킹 대신 반복적인 방법을 사용하여 모든 부분집합의 합을 생성합니다. 이 방법은 더 빠르고 메모리 효율적입니다.

이분 탐색: bisect_right 함수를 사용하여 오른쪽 그룹에서 조건을 만족하는 부분집합의 개수를 빠르게 찾습니다. 이는 시간 복잡도를 O(2^(N/2) * log(2^(N/2)))로 개선합니다.

입력 최적화: sys.stdin.readline()을 사용하여 입력 처리 속도를 높입니다.

이 알고리즘의 작동 방식은 다음과 같습니다:

물건들을 두 그룹으로 나눕니다.

각 그룹에 대해 가능한 모든 부분집합의 합을 계산합니다.

오른쪽 그룹의 부분집합 합을 정렬합니다.

왼쪽 그룹의 각 부분집합 합에 대해, 오른쪽 그룹에서 조건을 만족하는 부분집합의 개수를 이분 탐색으로 찾아 더합니다.

이 방법은 원래 코드의 정확성을 유지하면서도 더 효율적으로 문제를 해결합니다. 특히 N이 큰 경우에 더 좋은 성능을 보일 것입니다.

⚙️ 코드


import sys
from bisect import bisect_right

def input():
    return sys.stdin.readline().strip()

def generate_subsets(arr):
    subsets = [0]
    for num in arr:
        subsets.extend([subset + num for subset in subsets])
    return subsets

def count_combinations(N, C, weights):
    # 물건을 두 그룹으로 나눕니다
    mid = N // 2
    left_weights, right_weights = weights[:mid], weights[mid:]

    # 각 그룹에 대해 가능한 모든 부분집합의 합을 생성합니다
    left_sums = generate_subsets(left_weights)
    right_sums = generate_subsets(right_weights)

    # 오른쪽 그룹의 부분집합 합을 정렬합니다
    right_sums.sort()

    count = 0
    # 왼쪽 그룹의 각 부분집합 합에 대해
    for left_sum in left_sums:
        if left_sum > C:
            continue
        # 이분 탐색을 사용하여 조건을 만족하는 오른쪽 그룹의 부분집합 개수를 찾습니다
        count += bisect_right(right_sums, C - left_sum)

    return count

# 입력 처리
N, C = map(int, input().split())
weights = list(map(int, input().split()))

# 결과 출력
print(count_combinations(N, C, weights))

[백준] 1450 - 냅색문제

🖥️ 시작하며

⚙️ 코드

📌 소감

댓글