[Baekjoon] 12865번 : 평범한 배낭 (Python)

Python

방법 1 - 메모리 278216KB / 시간 5624ms / 코드 길이 363B

Knapsack(냅색) 문제로 분류되는 알고리즘 문제입니다.

무게의 최댓값이 정해져있을 때 가치의 최대값이 되는 문제로 DP로 풀어냅니다.

크게 2분류가 존재하는데 하나는 분할가능 배낭문제(Fractional Knapsack Problem)이고 또 다른 하나는 0-1 배낭문제(0-1 Knapsack Problem)입니다.

본 문제는 0-1 배낭 문제로 담는 물건이 담을지 말지를 결정하는 이진 문제입니다.

이 문제를 해결하기 위해 가치가 최대가 된다에서 DP 문제라는 것을 이해하실 수 있을 것입니다.

그러나 문제가 되는 것은 무게의 최댓값이 정해져있다는 것입니다.

이 부분을 해결하기 위해서 무게만큼의 길이의 list로 Memorization을 진행하는 것을 고려할 수 있습니다.

본 문제의 예시를 기반으로 설명드리겠습니다.

본 예시에서는 7의 무게가 최댓값으로 설정되어 있습니다.

Memorization을 위해서 총 8의 길이를 가지는 dp_list를 구성하겠습니다.

아래 표에서 우리가 하고자 하는 것은 각 열에 해당하는 숫자보다 클 때 허용가능한 무게의 최대 가치를 구하는 것입니다.

행에 대하여 순차적으로 진행되고 그 숫자의 가치에 대해 최대가 되는 것을 선택하고 참고되는 값으로 그 이전 값을 고려하는 것입니다.

결과적인 DP의 Memorization은 다음과 같이 나오게 됩니다.

무게➡	0	1	2	3	4	5	6	7
무게, 가치 (w,v) ⬇
6,13	0	0	0	0	0	0	13	13
4,8	0	0	0	0	8	8	13	13
3,6	0	0	0	6	8	8	13	14
5,12	0	0	0	6	8	12	13	14

아래 코드와 위 표를 참조할 때 가장 주의깊게 봐야하는 것은 3번째 행으로 아래 순서대로 진행된 값을 보겠습니다.

i=2

w,v=3,6

j < w=3

j=1 : d[2][1] = d[1][1] = 0

j=2 : d[2][2] = d[2][1] = 0

j ≧ w = 3

j=3 : d[2][3] = max(d[1][j-w]+v = d[1][0]+6 = 0+6=6, d[1][3] = 0) = 0

j=4 : d[2][4] = max(d[1][j-w]+v = d[1][1]+6 = 0+6=6, d[1][4] = 8) = 8

j=5 : d[2][5] = max(d[1][j-w]+v = d[1][2]+6 = 0+6=6, d[1][5] = 8) = 8

j=6 : d[2][6] = max(d[1][j-w]+v = d[1][3]+6 = 0+6=6, d[1][6] = 13) = 13

j=7 : d[2][7] = max(d[1][j-w]+v = d[1][4]+6 = 8+6=14, d[1][7] = 13) = 14

유심히 관찰하면 max로 값을 도출하는 부분에서 j-w에 해당하는 부분은 최대 무게값-본 무게값에 대한 dp의 덧셈인 것을 확인할 수 있습니다.

이 부분에 대한 이해가 되어야 이 문제에 대한 응용이 가능합니다.

import sys
input=sys.stdin.readline
n,k=map(int, input().split())
l=[list(map(int, input().split())) for _ in range(n)]
d=[[0]*(k+1) for _ in range(n)]
for i in range(n):
    w = l[i][0]
    v = l[i][1]
    for j in range(1,k+1):
        if j < w:
            d[i][j] = d[i-1][j]
        else:
            d[i][j] = max(d[i - 1][j-w]+v, d[i-1][j])
print(d[-1][k])

방법 2 - 메모리 33688KB / 시간 4216ms / 코드 길이 255B

방법 1의 연장선으로 d를 줄여보았습니다.

이와 관련한 코드는 다음과 같습니다.

import sys
input=sys.stdin.readline
n,k=map(int, input().split())
l=[list(map(int, input().split())) for _ in range(n)]
d=[0]*(k+1)
for w,v in l:
    for i in range(k,-1,-1):
        if i<w:
            break
        d[i] = max(d[i-w]+v, d[i])
print(d[k])

방법 3 - 메모리 33688KB / 시간 3636ms / 코드 길이 231B

if문을 제거하기 위해 2번째 for문을 수정하였습니다.

이를 통해 코드를 더 간소화 하였습니다.

다만 순서상의 문제가 있을 수 있기에 list에 대한 sort를 진행하였습니다.

import sys
input=sys.stdin.readline
n,k=map(int, input().split())
l=[list(map(int, input().split())) for _ in range(n)]
l.sort()
d=[0]*(k+1)
for w,v in l:
    for i in range(k,w-1,-1):
        d[i] = max(d[i-w]+v, d[i])
print(d[k])