백준 12865번 평범한 배낭(냅색) 파이썬 (python code)

난이도: 골드5
번호: 12865번

 

가장 평범한 dp 문제중 하나인 냅색 knapsack 문제이다.

 

그리디하게 풀려다가 안돼서 찾아보니 점화식을 이용한 다이나믹프로그래밍 문제인걸 알게되었다.

 

그래서 금방 풀줄 알았는데 너무 오래걸렸다.

 

중간에 작성한 오답코드

from sys import stdin

N, K = map(int,stdin.readline().split())
WV=[0]*(N+1)
for i in range(1,N+1):
    WV[i] = list(map(int,stdin.readline().split()))
knapsack=[[0]*(K+1)]*(N+1)

for i in range(1,N+1):
    for j in range(1,K+1):
        knapsack[i][j]=max(knapsack[i-1][j], knapsack[i-1][j-WV[i][0]]+WV[i][1]) if j>=WV[i][0] else knapsack[i-1][j]
print(knapsack[N][K])

처음에는 방법을 몰라서 헤메다가 나중에 

 

knapsack[i][j] = max(knapsack[i - 1][j], knapsack[i][j - WV[i][0]] + WV[i][1]) if j>=WV[i][0] else knapsack[i - 1][j]

 

여기서 문제가 발생한 줄 알고 if else로 나눴는데도 오답이 나왔다.

 

문제에서 각 아이템은 한번만 쓸 수 있다는것을 인지하지 못해서 위와같이 풀었는데

 

한 아이템은 하나밖에 사용하지 못하므로 i-1과 비교해야 했다.

if j>=WV[i][0]: 
        knapsack[i][j] = max(knapsack[i - 1][j], knapsack[i - 1][j - WV[i][0]] + WV[i][1]) 
else: 
        knapsack[i][j] = knapsack[i - 1][j]

 

그럼에도 틀려서 확인해보니 knapsack을

knapsack=[[0] * (K + 1)]*(M+1)

로 지정하면 행의 주소를 복사해버린다는 것을 인지하지 못하다가

마지막에 다른 코드를 보고

knapsack=[[0] * (K + 1) for _ in range(N + 1)]

로 변경하였다.

 

정답코드

from sys import stdin
N, K = map(int,stdin.readline().split())
WV=[0]*(N+1)
for i in range(1,N+1):
    WV[i] = list(map(int,stdin.readline().split()))
knapsack=[[0] * (K + 1) for _ in range(N + 1)]
for i in range(1,N+1):
    for j in range(1,K+1):
        if j>=WV[i][0]:
            knapsack[i][j] = max(knapsack[i - 1][j], knapsack[i - 1][j - WV[i][0]] + WV[i][1])
        else:
            knapsack[i][j] = knapsack[i - 1][j]
print(knapsack[N][K])