백준 1450번: 냅색문제 (Python)

접근

이 문제는 meet in the middle 이라는 알고리즘을 이용하여 푸는 문제이다. meet in the middle 알고리즘은 말그대로 한번에 연산하기 어려운 문제를 둘로 나누어 시간적인 단축을 꾀하는 알고리즘이다. 위 문제같은 경우 만약 주어진 n 이 30이라면, 부분 집합의 합은 각 원소가 있고 없고를 카운트하여 2 ^ 30의 경우의 수를 가지게 된다. 즉 2 ^ n 의 시간복잡도를 가지게 되는 것이다. 하지만 이를 반으로 나누어 2 ^ 15 정도만 되어도 기존에 비해 매우 할만해지는 숫자가 되기 때문에 meet in the middle 알고리즘을 사용하게 된다.

이 문제를 푸는 순서는 다음과 같다.

1. weight 리스트를 반으로 나눈다. 보통 len(weight) // 2 를 기준으로 나누게 되고 이를 a_weight, b_weight 라고 부를 것이다.
2. a_weight, b_weight 각각을 브루트포스 방법으로 부분 집합의 합을 구해주고 이를 a_sum, b_sum 에 모두 추가해준다.
3. b_sum 을 binary search 하기 위해 오름차순으로 정렬해준다.
4. a_sum 의 원소 i에 대하여 c - i 값보다 작거나 같은 수 중 가장 큰 값을 정렬된 b_sum에서 찾아준다.
5. 이때 찾아진 수보다 작은 수들은 모두 c보다 작아 가방에 넣을 수 있기 때문에 (4)에서 찾아진 수보다 작은 b_sum 값들 개수만큼 카운트해준다.

결론적으로는 weight 를 절반으로 나누어 각각을 브루트포스 방법으로 부분 집합을 구하고, a 부분 집합과 b 부분 집합의 합이 c 보다 작은 값들을 카운트 해주는 방법인 것이다.

코드

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 = []


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])


def binarysearch(arr, target, start, end):
    while start < end:
        mid = (start + end) // 2
        if arr[mid] <= target:
            start = mid + 1
        else:
            end = mid
    return end


bruteforce(aw, asum, 0, 0)
bruteforce(bw, bsum, 0, 0)
bsum.sort()

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

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!