백준 1450번: 냅색문제 [python]

kimminjunnn·2025년 7월 5일

백준 알고리즘

알고리즘

목록 보기

116/311

난이도 : 골드 1
유형 : 투 포인터
https://www.acmicpc.net/problem/1450

문제 접근

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.

-> 물건 개수 : N, 가방의 적재할 수 있는 최대 무게 :C

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, C
둘째 줄에 공백을 기준으로 N개 물건의 무게를 입력받는다.

출력

N개의 물건을 가방에 넣는 방법의 수

우선 물건은 다 서로 다른 물건이다. 그리고 물건은 넣을 수 있고 안 넣을 수 있다.
C 이하의 무게를 싣는 선에서 물건을 넣을 수 있는 경우의 수를 구해야한다.

.
.
.
모르겠다 지피티에게 물어봤다.

지피티의 답

N이 최대 30이라서 부분집합의 개수는 2³⁰ ≈ 10억 → 완전 탐색은 ❌
하지만 N이 작으니까 "Meet in the Middle" (중간에서 만나기) 전략을 사용해야 해!

라고 한다.

그리고 이진 탐색을 사용하는데 이전에 이진 탐색을 사용한 적이 있다.

백준 1020번: 수 찾기

하지만 그 때는 라이브러리를 사용하지 않았으며, 하물며 이진탐색 기법의 기억도 희미하니 기억도 리마인드하고, bisect라는 라이브러리를 공부할겸 다시 이진탐색을 정리하겠다.

이진탐색

개념
정렬된 배열에서 원하는 값을 빠르게 찾기 위해 반씩 줄여가며 탐색하는 알고리즘.
시간 복잡도: O(log N)
기본형태

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  # 찾으면 인덱스 반환
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # 못 찾으면 -1

맞다. mid를 설정해주고 target과 비교해가며 좌우 포인터값을 이동해주는 방식이었다.
파이썬에서는 bisect 모듈로 이진 탐색을 간편하게 할 수 있다.

bisect
bisect는 정렬된 배열에서 이진 탐색을 쉽게 할 수 있게 도와주는 모듈이다.
삽입 위치 찾기와 정렬 유지하면서 삽입하기에 특화되어 있다.

주요함수 4개는 다음과 같다.

함수	기능	설명
`bisect_left(a, x)`	x값 이상이 처음 나오는 위치(인덱스) 반환	중복된 값이 있을 경우 가장 왼쪽 인덱스
`bisect_right(a, x)`	x값 초과가 처음 나오는 위치(인덱스) 반환	중복된 값이 있을 경우 가장 오른쪽 인덱스 + 1
`insort_left(a, x)`	`bisect_left` 위치에 x를 삽입	정렬 유지하면서 삽입
`insort_right(a, x)`	`bisect_right` 위치에 x를 삽입	정렬 유지하면서 삽입

import bisect

arr = [1, 3, 3, 5, 7]

# 이진 탐색 위치 찾기
print(bisect.bisect_left(arr, 3))   # 결과: 1
print(bisect.bisect_right(arr, 3))  # 결과: 3

# 삽입하기
bisect.insort_left(arr, 3)
print(arr)  # [1, 3, 3, 3, 5, 7]

bisect.insort_right(arr, 3)
print(arr)  # [1, 3, 3, 3, 3, 5, 7]

bisect를 사용한 이진 탐색 코드

import bisect

def binary_search(arr, target):
    # arr는 반드시 정렬되어 있어야 함
    idx = bisect.bisect_left(arr, target) # target 이상의 값이 제일 먼저 나오는 index 값
    
    # idx가 배열 범위 안이고, 해당 위치 값이 target과 같다면 찾은 것
    if idx < len(arr) and arr[idx] == target:
        return idx  # 값의 위치 반환
    else:
        return -1   # 값이 없음

# 예시
arr = [1, 3, 3, 5, 7, 9]
target = 3

result = binary_search(arr, target)
print("찾았다!" if result != -1 else "없다!", result)

idx = bisect_left(arr, target)
이 강력한 한줄로 원하는 인덱스값을 찾을 수 있다는 점에서 bisect 모듈을 활용하지 않을 이유가 없다는 것을 확인했다.

다시 Meet in the Middle 전략 + bisect 조합 을 활용해 1450번을 풀어보겠다.

문제 재접근

물건을 고를 수도 있고 안 고를 수도 있어
모든 경우의 수 = 부분집합의 수 = 2^N 개
그중에서 무게 합이 C 이하인 경우만 센다.

핵심 아이디어

[1,2,3] 물건이 있고 무게 제한이 3이라면

조합	무게 합(부분 합)
`[]`	0
`[1]`	1
`[2]`	2
`[3]`	3
`[1,2]`	3
`[1,3]`	4 ❌
`[2,3]`	5 ❌
`[1,2,3]`	6 ❌

이렇게 2^3 = 총 8개 중 답은 5가 된다.

이 때 우리는 어떤 조합을 했는지 파악하는 것은 중요하지 않고, 그저 가짓수만 구하면 된다.

그러니 선택한 조합의 합인 부분 합 을 통해 구하면 편하다.
왜냐면 어차피 총 무게 C와 비교해야하기 때문이다. 그리고 [1,2]와 [2,1] 은 똑같기 때문이다. 같은 물건이니까 순서는 중요하지 않기에!

고로
모든 부분합을 리스트로 구하고,
C 이하인것들을 찾으면 끝이다.

부분합을 리스트로 표현하는 것은
비트 연산자를 통해 할 수 있는데 이 부분 이해가 너무 어려웠다.
일단 꾸역꾸역 이해하고 넘어가는데 다음에 나오면 다시 익혀봐야겠ㄷ다.

# 주어진 배열에서 가능한 모든 부분합을 구하는 함수
def get_subset_sums(arr):
    result = []
    n = len(arr)

    # 총 부분집합의 개수는 2^n
    for i in range(1 << n):
        # 비트 연산자 << 는 숫자 x를 2진수로 생각해서, 왼쪽으로 n칸 밀어라! 그래서 1 << n 는 2^n이 된다.
        total = 0  
    
        # i  번째 조합을 확인 (i는 0부터 2^n-1 까지))
        for j in range(n):
            # j번째 물건이 선택됐는지 확인 (i를 이진수로 보면 됨)
            if i & (1 << j):  # j번 물건을 선택했는지 확인
                # "i의 이진수에서 j번째 비트가 켜졌는가?"
                # 즉, "j번째 물건이 선택됐는가?"
                total += arr[j]
        result.append(total)

    return result

해답 및 풀이

from bisect import bisect_right
import sys
input = sys.stdin.readline

# 주어진 배열에서 가능한 모든 부분합을 구하는 함수

def get_subset_sums(arr):
    result = []
    n = len(arr)

    # 총 부분집합의 개수는 2^n
    for i in range(1 << n):
        # 비트 연산자 << 는 숫자 x를 2진수로 생각해서, 왼쪽으로 n칸 밀어라! 그래서 1 << n 는 2^n이 된다.
        total = 0  
    
        # i  번째 조합을 확인 (i는 0부터 2^n-1 까지))
        for j in range(n):
            # j번째 물건이 선택됐는지 확인 (i를 이진수로 보면 됨)
            if i & (1 << j):  # j번 물건을 선택했는지 확인
                # "i의 이진수에서 j번째 비트가 켜졌는가?"
                # 즉, "j번째 물건이 선택됐는가?"
                total += arr[j]
        result.append(total)

    return result


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

# 1. 물건을 반으로 나눈다
left = weights[:N // 2]
right = weights[N // 2:]

# 2. 각각의 부분집합 합을 구한다
left_sums = get_subset_sums(left)
right_sums = get_subset_sums(right)

# 3. 오른쪽 부분합 리스트를 정렬 (bisect를 쓰기 위해)
right_sums.sort()

# 4. 가능한 조합 수 계산
count = 0
for a in left_sums:
    remain = C - a
    # right_sums에서 remain 이하인 원소의 개수 구하기
    count += bisect_right(right_sums, remain)

# 출력
print(count)

전체 코드이다.
bisect_right을 통해 부분에서 C - a 이하인 애들만 찾아줘서 count에 추가해준다.

비트마스크 개념과 bisect 개념을 처음 접해서 현재 내겐 너무 어려운 문제였다.

다음에 봤을 때 조금 더 쉬워보였으면 좋겠다.

이 문제 bisect가 아닌 투포인터를 활용해서 풀 수도 있다고 한다.

meet me in the middle + 투 포인터 활용 코드

def get_subset_sums(arr):
    result = []
    n = len(arr)
    for i in range(1 << n):
        total = 0
        for j in range(n):
            if i & (1 << j):
                total += arr[j]
        result.append(total)
    return result

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

# 절반으로 나누기
left = weights[:N // 2]
right = weights[N // 2:]

# 부분합 구하기
left_sums = get_subset_sums(left)
right_sums = get_subset_sums(right)
right_sums.sort()

# 투포인터로 가능한 조합 수 구하기
count = 0
j = len(right_sums) - 1

for a in left_sums:
    # right_sums에서 a + b > C인 b는 버린다
    while j >= 0 and a + right_sums[j] > C:
        j -= 1
    count += (j + 1)  # b가 0부터 j까지는 모두 가능

print(count)