99클럽 코테 스터디 3일차 TIL + 냅색문제

1. 문제 상황

• 문제 이름: 냅색문제 (백준 1450번)
• 문제 설명: N개의 물건이 있고, 각 물건의 무게가 주어진다. 가방에 담을 수 있는 최대 무게는 C이다. 이때, 가방에 담을 수 있는 물건들의 조합 수(부분집합의 합이 C 이하인 경우)를 구하는 문제다.
• 제한사항:
  • N ≤ 30이므로 모든 부분집합을 계산하면 2^30으로 비효율적
  • C는 최대 10^9까지 가능하여 DP 방식의 배열 접근이 어려움🧠 문제 접근
    • 무게가 있는 n개의 물건이 있다. 이 중 몇 개를 골라 가방에 넣을 수 있는데, 가방에 담을 수 있는 최대 무게는 C이다.
    • 조건을 만족하는 물건 조합의 수를 구해야 한다.
    • 단, n의 최대가 30이기 때문에 부분집합 개수는 2³⁰ ≒ 10⁹으로 완전탐색은 시간 초과.

    ---

    🤔 문제 해결 아이디어
    • n이 30이므로, 배열을 절반으로 나누어 처리하는 Meet in the Middle 기법이 적절함.
    • 배열을 반으로 나누고, 각각의 부분집합을 모두 만든 후 두 배열에서 조합 가능한 쌍의 수를 계산.
    • a_list, b_list로 나눈 뒤, 정렬하여 투 포인터 방식으로 조건을 만족하는 쌍을 셈.

✅ 코드

from itertools import combinations

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

# 배열 반으로 나누기
mid = n // 2
a = arr[:mid]
b = arr[mid:]

a_list = [0]
b_list = [0]

# a, b 각각 부분집합의 합 구하기
for i in range(1, len(a) + 1):
    for comb in combinations(a, i):
        a_list.append(sum(comb))

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

a_list.sort()
b_list.sort()

# 투 포인터
count = 0
s = 0
e = len(b_list) - 1

while s < len(a_list) and e >= 0:
    if a_list[s] + b_list[e] <= c:
        count += e + 1
        s += 1
    else:
        e -= 1

print(count)

💡 배운 점 & 느낀 점

• Meet in the Middle 기법은 처음 사용해봤는데, n이 작을 때 정말 유용한 방법이라는 걸 알게 되었다.
• 완전탐색과 조합으로도 계산이 가능하지만, 효율을 고려하지 않으면 시간 초과가 나는 것을 체감했다.
• combinations로 부분집합의 합을 구하고, 정렬한 리스트를 활용하여 투 포인터를 적용하는 방식이 직관적이고 깔끔했다.

---

📚 내일 공부할 것

• bisect를 활용한 이분 탐색 방식으로도 문제를 해결해보기 (bisect_right 등)
• Meet in the Middle 유형 문제 더 풀어보기
• 투 포인터와 이분 탐색 차이점과 활용법 정리