(Python) 백준 12865

백준 12865

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	95793	35487	22917	35.418%

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

---

답안

import sys

input = sys.stdin.readline
n, max_weight = map(int, input().split())
bag = [[0, 0]] + [list(map(int, input().split())) for _ in range(n)]
prev, curr = [0] * (max_weight+1), []

for i in range(1, n+1):
    weight, value = bag[i]
    curr = prev[:]
    if weight <= max_weight:
        curr[weight] = max(curr[weight], value)
    for j in range(1, max_weight-weight+1):
        curr[weight+j] = max(curr[weight+j], prev[j] + value)
    prev = curr[:]

print(max(curr))

풀이

처음에는 모든 물품을 무게, 가치, 또는 가치/무게와 같은 기준으로 sort를 한 뒤, 가방 안에 들어갈 물품의 조합을 찾는 알고리즘을 생각해냈고, 다만 어떻게 해야 그 조합을 찾는 경우의 수를 줄일 수 있을까 생각을 했었다.

하지만 그렇게 조합을 찾는 알고리즘은 어떻게 짜더라도 $O(n^3)$의 시간복잡도를 가졌고, 물품의 수 n의 최댓값이 100, 최대 무게 k의 최댓값이 100만인 상황에서, 가장 최악의 경우 2초의 시간 제한을 지킬 수 없을 것 같았다.

그렇다고 해도, 그리디 방법을 사용하는 것은 불가능했는데, 지역적인 최적해의 집합이 전체 최적해로 이어지지 않았기 때문이다.

이 문제를 풀기 위해 그 다음으로 생각했던 방법은 DP였다. 이전에 싸 놓은 최적의 배낭으로 지금의 최적의 배낭을 쌀 수 있을 것이라고 생각했기 때문이다.

하지만, 어떻게 최적의 배낭을 구할지 그 구체적인 방법을 구하지 못해 해멨었다.

최대 무게가 1, 2, 3, …, k일 때 최적의 배낭을 구하는 방법을 생각해보았지만, 만약 아래와 같은 경우

item_no	weight	value
1	3	5
2	6	7
3	8	11

최대무게에 따른 물건 가치합의 최댓값을 구하면

max_weight	max_value_sum	item_no
1	0	-
2	0	-
3	5	1
4	5	1
5	5	1
6	7	2
7	7	2
8	11	3
9	12	1+2
10	12	1+2

으로, 이전 배낭을 통해 현재 최적의 배낭을 구하는 것이 어렵다.

그 이유로는 어떤 이전 최적 배낭을 이용해야 하는지 명확하지 않고, 같은 max_weight를 가지는 배낭이라도, 다양한 경우의 수로 최적 배낭을 짤 수 있기 때문이다.

또한 max_weight수치가 작을 때의 최적의 배낭이 아니라서 버려진 경우의 수가, 이후 max_weight 수치가 높을 때 물건을 더해 최적의 배낭이 되는 경우가 있기 때문에, 무언가 다른 방법을 사용해야만 모든 경우의 수를 탐색하지 않고 문제를 풀 수 있었다.

문제가 풀리지 않아 막힌 도중, 아래 글에서 2차원 배열 메모이제이션을 통해 문제를 접근하는 방법을 참고한 뒤 문제 해결의 실마리를 얻었다.

https://velog.io/@lre12/백준-12865번-평범한-배낭

위 문제가 발생하는 때는 다음과 같다. 최대 무게보다 적게 채웠을 때의 가치의 합이 그 당시의 최대 가치 합보다 낮아 메모이제이션되지 않는 경우에, 최대 무게보다 적게 채웠을 때의 배낭이 다음에 사용되어 전체 최적해가 될 때이다.

따라서 메모이제이션의 차원을 하나 더 늘려서, 최대 무게와 현재 무게 각 두 개의 기준에 따른 최대 가치합을 기록할 필요가 있다.

예를 들자면 다음과 같다. (n=3, max_weight=10일 때)

item_no	weight	value
1	3	5
2	6	7
3	8	11

input \ weight	1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0	0
1 (3, 5)	0	0	5	5	5	5	5	5	5	5
2 (6, 7)	0	0	5	5	5	7	7	7	12	12
3 (8, 11)	0	0	5	5	5	7	7	11	12	12

위 표의 행은 들어온 입력을, 열은 그 때 가방에 들어있는 weight에 따른 지금까지의 최적의 가방을 나타낸다. max_weight = 10이라고 가정하였으므로, 10을 넘는 weight를 가지는 가방은 존재하지 않는다.

가장 먼저 weight=3, value=5 (3, 5)를 입력받는 상황을 살펴보자. (표의 input 1 행)

가방에 들어있는 weight가 3일 때에는 1번 물건을 넣어 가치 5를 얻는 것이 가능하다. 이는 3<weight≤10인 경우에도 가능하다. weight가 3 이상인 배낭들에서 이전(0)보다 얻는 가치가 크므로, 5로 수정한다.

다음으로 (6, 7)을 입력받으면 (표의 input 2행),

무게가 6 이상인 배낭의 경우, 2번 물건을 넣어 가치 7을 얻는 것이 가능하다. weight가 6 이상인 배낭들에서 경우 이전(5)보다 얻는 가치가 크므로, 값을 7로 수정한다.

가방에 들어있는 weight가 3 또는 4일 때는 무게 6짜리 물건을 더 넣어 가치 12를 만드는 것이 가능하다.

따라서 이 과정을 정리하면 다음과 같다.

1. 이전 배열을 복사한다.
2. input으로 들어온 물품 하나를 집어넣었을 때 최적해가 되는지 확인한다.
3. 이전의 배낭들에 input으로 들어온 물품 하나를 집어넣었을 때 최적해가 되는지 판단한다.

• 배낭들에 물품을 집어넣을 때 최대 무게를 넘어서는 안된다.

그것을 코드로 옮긴 것이 아래이다.

import sys

input = sys.stdin.readline
n, max_weight = map(int, input().split())
bag = [[0, 0]] + [list(map(int, input().split())) for _ in range(n)]
prev, curr = [0] * (max_weight+1), []

for i in range(1, n+1):
    weight, value = bag[i]
    curr = prev[:]
    if weight <= max_weight:
        curr[weight] = max(curr[weight], value)
    for j in range(1, max_weight-weight+1):
        curr[weight+j] = max(curr[weight+j], prev[j] + value)
    prev = curr[:]

print(max(curr))

위에서는 2차원 표를 사용했지만, 이전 배열과 현재 배열 (크기 = max_weight) 을 제외한 배열은 다음 계산에서 사용되지 않기 때문에, 크기가 max_weight인 배열 curr과 prev만 사용된다.

배열 curr과 prev는 크기가 max_weight인 배열에서 동작할 수 있지만, weight가 1일 때 index 1번을 사용하기 위해 크기를 max_weight + 1로 하였다.

가장 핵심 코드는 다음이다.

for i in range(1, n+1):
    weight, value = bag[i]
    curr = prev[:]
    if weight <= max_weight:
        curr[weight] = max(curr[weight], value)
    for j in range(1, max_weight-weight+1):
        curr[weight+j] = max(curr[weight+j], prev[j] + value)
    prev = curr[:]

모든 n에 대해,

curr[weight] = max(curr[weight], value)

이전 최적해 배낭보다 지금 입력된 물건의 value가 더 높은지 확인하고,

curr[weight+j] = max(curr[weight+j], prev[j] + value)

이전 최적해 배낭에 지금의 물건을 넣었을 때 더해진 weight에서 최적해가 되는지 확인한다.

마지막으로 loop를 돈 뒤 curr 배열에는 각 weight만큼 배낭에 물건을 넣었을 때의 각각의 최적해 값이 들어가 있다.

print(max(curr))

curr 배열의 최댓값을 출력하면 정답으로 인정된다.