[백준] 1450 - 냅색문제

https://www.acmicpc.net/problem/1450

 

문제 풀이

 

주어진 물건들을 가방 안에 담을 수 있는 모든 경우의 수를 출력하는 문제

나이브하게 접근하면 물건이 최대 30개 있으므로, 2^30 조합을 모두 시도해보면 된다.

하지만 이렇게 접근하면 최악의 경우 1,073,741,824 가지의 경우의 수가 나오기 때문에 시간초과가 발생한다.

따라서 meet in the middle 테크닉을 이용하여 시간을 줄이는 것이 이 문제의 핵심이다.

 

'중간에서 만나기' 라는 이름으로도 불리는 이 테크닉은, 사이즈가 큰 전체 대상을 처음부터 끝까지 직접 탐색하는 것보다,

전체 영역을 반으로 나눈 뒤, 반씩 쪼개서 탐색한 결과를 조합하여 해답을 구하는 기법이다.

 

이 문제의 경우, 2^30의 조합을 모두 구하는 것은 힘들지만,

2^15 조합을 두번 탐색하는 경우 각각 32768 가지의 경우를 탐색하면 되므로 충분히 시간 안에 탐색할 수 있다.

32768 가지의 경우를 탐색해서, 각 경우마다 그때의 무게로 담을 수 있다면, 해당 무게에 대해 count 를 증가시키는 식으로 센 뒤에, 첫번째 조합에서 가능한 무게 조합, 두번째 조합에서 가능한 무게 조합을 곱해서 답을 구할 수 있다.

 

나는 무게로 가능한 범위가 최대 1억이라서, 배열대신 해시맵을 사용하여 무게별 가능한 경우의 수를 저장했다.

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

weight_dict1 = dict()
weight_dict2 = dict()

 

그래서 이렇게 2개의 딕셔너리를 만들었다.

 

이제 각각의 딕셔너리를 채우기 위해 다음과 같은 재귀함수를 작성했다.

def count_weight(weight_index, max_index, now_sum, weight_dict):
    if weight_index == max_index:
        if not now_sum in weight_dict:
            if now_sum <= c:
                weight_dict[now_sum] = 1
        else:
            weight_dict[now_sum] += 1
        return
    count_weight(weight_index+1, max_index, now_sum, weight_dict)
    count_weight(weight_index+1, max_index, now_sum + weights[weight_index-1], weight_dict)


count_weight(1, n//2+1, 0, weight_dict1)
count_weight(n//2+1, n+1, 0, weight_dict2)

 

2^15 조합별로, 해당 조합으로 만들어진 무게가 가방에 들어갈 수 있는 무게라면 딕셔너리에 저장한다.

이 함수의 인자로 사용된 index는 1-index 이다.

가방에 아무것도 넣지 않았을 때도 세어야 하기 때문이다.

 

 

예제입력 1번에 대해서 이 함수를 실행한 뒤, 두 딕셔너리를 출력해보면 위와 같이 나온다.

첫번째 조합(첫번째 1)에 대해서는 무게가 0인 경우의 수 1개, 무게가 1인 경우의 수가 1개

두번재 조합(두번째 1)에 대해서는 무게가 0인 경우의 수 1개, 무게가 1인 경우의 수가 1개 이다.

 

이제 이 둘을 조합하면 된다.

두 딕셔너리의 키(무게)를 순회하면서, 두 무게의 합이 가방의 제한 무게 이하라면 그 각각의 경우의 수를 곱해서 정답에 더해준다.

 

---

 

하지만 이렇게 해서 이 문제가  풀린다면 골드1이 되지 않았을 것이다..

이 문제는 이렇게 풀면 시간초과가 발생한다.

첫번쩨 조합에서 가능한 무게의 가짓수를 W1, 두번째 조합에서 가능한 무게의 가짓수를 W2 라고 하면,

위 방식의 시간복잡도는 O(W1 W2) 로, 두 조합이 유사하다면 O(W²) 에 근사한 시간이기 때문이다.

 

시간을 줄이기 위해서 이분탐색을 사용할 수 있다.

 

W1 무게 일 때, 만약 W2 무게가 가능했다면

W2-1, W2-2, ....., 0 무게에 대해서도 모두 가능하다는 것이 보장된다.

 

따라서, 두번째 딕셔너리에는 무게 순으로 정렬했을 때, 경우의 수가 누적합으로 저장되도록 바꾸고

W1 이 결정되었을 때 사용할 수 있는 가장 큰 W2 를 이분탐색으로 찾으면 O(W log W) 시간에 풀 수 있다.

 

answer = 0
weight_dict2_keys = sorted(weight_dict2.keys())
for i in range(1, len(weight_dict2_keys)):
    weight_dict2[weight_dict2_keys[i]] += weight_dict2[weight_dict2_keys[i-1]]

for key1 in sorted(weight_dict1.keys()):
    left, right = 0, len(weight_dict2_keys)
    while left + 1 < right:
        mid = (left + right) // 2
        if key1 + weight_dict2_keys[mid] <= c:
            left = mid
        else:
            right = mid

    key2 = weight_dict2_keys[left]
    answer += weight_dict1[key1]*weight_dict2[key2]

print(answer)

 

이를 구현한 코드는 위와 같다.

---

최종 정답 코드

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

weight_dict1 = dict()
weight_dict2 = dict()


def count_weight(weight_index, max_index, now_sum, weight_dict):
    if weight_index == max_index:
        if not now_sum in weight_dict:
            if now_sum <= c:
                weight_dict[now_sum] = 1
        else:
            weight_dict[now_sum] += 1
        return
    count_weight(weight_index+1, max_index, now_sum, weight_dict)
    count_weight(weight_index+1, max_index, now_sum + weights[weight_index-1], weight_dict)


count_weight(1, n//2+1, 0, weight_dict1)
count_weight(n//2+1, n+1, 0, weight_dict2)

answer = 0
weight_dict2_keys = sorted(weight_dict2.keys())
for i in range(1, len(weight_dict2_keys)):
    weight_dict2[weight_dict2_keys[i]] += weight_dict2[weight_dict2_keys[i-1]]

for key1 in sorted(weight_dict1.keys()):
    left, right = 0, len(weight_dict2_keys)
    while left + 1 < right:
        mid = (left + right) // 2
        if key1 + weight_dict2_keys[mid] <= c:
            left = mid
        else:
            right = mid

    key2 = weight_dict2_keys[left]
    answer += weight_dict1[key1]*weight_dict2[key2]

print(answer)