[백준] 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)