백준 12865 평범한 배낭 파이썬 문제풀이 (python 바텀업 DP)

문제 보러가기

 

백준 평범한 배낭 파이썬 문제풀이 바텀업 DP

배낭 문제를 이번에는 bottom up DP를 이용한 방법으로 풀어본다.

재귀를 이용하지 않고 반복문 만으로 푸는 것이다.

 

그러려면 2차원 dp로 보았을 때, 

각 축은 index와 weight이다.

 

현재 index 및 무게에 해당하는 가치를 

다음 index 및 무게 위치에 넣는 방식으로 구성된다.

 

우선 index를 차례로 돌면서

각 index마다 weight dp를 순환하는 반복문 안에서 진행된다.

 

for i in range(n):
    for wgt in range(1, k+1):

        if wgt < stuff[i][0]:
            dp[i+1][wgt] = dp[i][wgt]
        else:
            dp[i+1][wgt] = max(dp[i][wgt - stuff[i][0]] + stuff[i][1],
                            dp[i][wgt])

현재 인덱스에 들어오는 물건의 무게보다 무게가 적은 dp값의 경우

다음 dp에 현재 dp value를 그대로 대입한다.

 

왜냐하면 현재 인덱스 무게까지 얻을 수 있는 물건 가치의 최대값을

이미 dp[index][weight]가 가진 상태이기 때문에 그대로 넣어주면 된다.

 

만약 현재 인덱스 물건의 무게보다 큰 무게의 dp값들의 경우는 케이스가 갈린다.

dp[index][weight]에서 weight가 stuff의 w값보다 큰 상황을 말한다.

 

이 경우 dp의 진 면모 max 함수로 최대가 되는 값을 넣어야한다.

즉 다음 index의 dp값에

현재 인덱스의 dp값이 현재 인덱스 물건이 포함되지 않은 경우인지

아니면 포함된 경우인지 중 더 큰 dp값을 넣는다.

 

여기가 어렵다...

 

dp[i+1][wgt] = max(dp[i][wgt - stuff[i][0]] + stuff[i][1], dp[i][wgt])

max의 첫 인자가 현재 물건이 포함된 경우이고,

두 번째가 포함되지 않아서 무게도 가치도 그대로인 경우이다.

 

포함된 경우는 다음 dp의 무게 wgt가 현재 dp의 무게에서 물건의 무게를 제외한 값이 되어야한다.

그래서 wgt - stuff[i][0] 를 하는 것.

물건의 가치는 dp에 더해지므로 stuff[i][1]은 더해준다.

 

정답 코드

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

for i in range(n):
    w,v = map(int,input().split())
    stuff.append([w,v])

for i in range(n):
    for wgt in range(1, k+1):

        if wgt < stuff[i][0]:
            dp[i+1][wgt] = dp[i][wgt]
        else:
            dp[i+1][wgt] = max(dp[i][wgt - stuff[i][0]] + stuff[i][1],
                            dp[i][wgt])

print(dp[n][k])

인덱스 i를 처리하는 것과

무게 wgt에서 stuff 무게를 빼서 2차원 배열에서 현재 무게 위치를 가져오는 방법이

상당히 이해하기 어려웠다.

 

어디까지나 다음 dp의 무게는 현재 dp의 무게에서 물건의 무게가 더해진 상태라는 것을 인지해야한다. 

구하는 값이 다음 dp 기준이기 때문에 현재 wgt를 구하기 위해 물건의 무게를 뺀다는 것.

지금은 온전히 이해하지 못해도 괜찮다 또 하면 된다~^^