[Baekjoon] 12865 평범한 배낭 (python)

문제 링크

link 📃 

문제 풀이

• dp문제의 가장 기본적인 문제라 오랜만에 다시 풀었다.
• n은 주어지는 물건의 갯수, k는 넣을 수 있는 최대 무게였고 무게배열 w[n+1], 가치배열 v[n+1]를 두고 dp[n+1][k+1]만큼의 dp 배열을 만들어주었다.
• 총 for 문이 2개가 돌면서 가장 큰 가치를 넣는 dp배열을 만들었고 마지막에 dp[n][k]를 return하면 완료하도록 짰다.
• 첫번째 for문은 n(물건의 갯수)까지 증가시킨다. 물건 배열을 입력때 받았던 순서대로 증가시킨다.
• 두번째 for문은 k(무게)까지 증가시키면서 넣을 수 있는 무게에 따른 가치 값을 넣어준다.
• 따라서 dp[1][7] 이면 첫번째 물건만 파악했을때 7의 무게까지 가질수 있는 dp의 값에 가장 큰 가치를 넣는다.
• 만약 현재 넣는 물건이 고려하는 무게가 클 경우는 그 물건을 넣기 전의 가치 값을 넣어준다. 따라서 dp[i-1][j]가 된다.
• 그렇지 않을 경우는 2가지를 비교해서 넣으면 되는데,
  1. (dp[i][지금 가질 수 있는 최대 무게 - 현재 그 물건의 무게] + 현재 물건의 가치)
  2. 현재 물건을 안넣고 이전 물건까지 고려했을 떄의 가치 => dp[i-1][j]
  
• 두 가지를 고려하여 큰 값을 dp[i][j]에 넣는 방식으로 진행한다.

해결 코드

Python

n, k = map(int, input().split())

w = [0 for _ in range(n+1)]
v = [0 for _ in range(n+1)]
dp = [[0 for _ in range(k+1)]for _ in range(n+1)]

for i in range(1,n+1):
    w[i], v[i] = map(int, input().split())
    
for i in range(1,n+1):
    for j in range(1, k+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max( (dp[i-1][j-w[i]] + v[i]), dp[i-1][j])
            
print(dp[n][k])