[백준] 12865 평범한 배낭(Python)

1. 문제 조건

• N개의 물건이 있고 각 물건은 무게 W와 가치 V를 가짐
• 무게 K까지 담을 수 있을 때 물건의 가치합 최대값 구하기

 

2. 풀이 전 생각정리

• 각각의 물건을 한번씩 훑으며 가능한 모든 경우에 대한 가치합을 리스트에 저장한다.
• 무게 7까지 담을 수 있고 물건 2개의 (무게, 가치)가 (2,3), (4,2)라면

		3
		3		2		5

이런 식으로 저장하며 물건들의 가치합 최댓값은 5 임을 알 수 있다.

• 무게 합이 K를 초과하는 경우에는 담을 수 없음을 고려한다.

 

3. 테스트 케이스만 통과한 코드

N, K = map(int, input().split())
mapp = []
for _ in range(N):
    W, V = map(int, input().split())
    mapp.append([W,V])
    
dp = [[0]*(K+1) for _ in range(N+1)]

for i in range(1,N+1): #1~N
    for j in range(K+1): #0~K
        #넣는 것 시작할 수 있는지
        if j == mapp[i-1][0] and mapp[i-1][0]<=K:
            dp[i][j] = max(dp[i-1][j], mapp[i-1][1])
        if dp[i-1][j] != 0:
            if j + mapp[i-1][0] <=K:
                dp[i][j + mapp[i-1][0]] = max(dp[i-1][j], dp[i-1][j] + mapp[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]


print(max(dp[N])

 

4. 성공 코드

• 시작하는데 시간이 조금 걸리더라도 모든 상황을 고려할 수 있는 깔끔한 점화식을 생각해 놓은 이후 코드를 짜는 것이 효율적인 것 같다.

N, K = map(int, input().split())
dp = [[0]*(K+1) for _ in range(N+1)]


for i in range(1,N+1): #1~N
    W, V = map(int,input().split())
    for j in range(K+1): #0~K
        if j<W:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-W]+V)        

print(max(dp[N]))