[Python] 백준 12865번: 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

문제를 분석해보면, 전형적인 냅색 문제이다. 아래 사진을 보자.

각 열은, 해당 물건을 필수적으로 가져간다고 했을 때의 총 가치를 나타낸다. 점화식은 아래와 같다.

DP[i][j] = DP[i][j-1] 또는 (현재 물건의 가치) + DP[0~i-1][j-(현재 물건의 무게)]의 최댓값

즉, dp[2][7]을 구할 때, 위의 사진과 같이 구했다는 것이다. 이것을 코드화 했을 때 중요한 포인트가 있다. 바로 해당 열에서의 max값을 어떻게 구하냐는 것이다. 나는 maxDp라는 배열을 도입하여 시간을 단축시켰다. 위 사진에서의 maxDp는 [0, 0, 0, 0, 8, 8, 13, 13]이다. 즉, 이전 열까지의 dp의 최댓값을 저장하는 배열이다. 주의해야할 점은, 현재 열에 대해서 dp값에 대입연산을 모두 마친 후에 maxDp를 갱신시켜야한다는 점이다. 이것을 코드화하면 아래와 같다.

 

import sys
input = sys.stdin.readline


if __name__ == '__main__':
    N, K = map(int, input().split())

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

    for i in range(N):
        w, v = map(int, input().split())

        for j in range(w, K+1):
            dp[i][j] = max(dp[i][j-1], v + maxDp[j-w])

        for j in range(w, K+1):
            maxDp[j] = max(maxDp[j], dp[i][j])
            
    print(max(dp[i][K] for i in range(N)))

 

---

 

하지만, 위에서 이용한 maxDp만으로 풀어낼 수 있다. 위에서는 j에 대한 for문을 2번을 써서 maxDp의 값이 dp가 갱신되면 바뀌도록 구분해놓았다. 하지만, for문을 거꾸로 돌면 시간, 공간복잡도가 매우 단축된다. 이렇게 함으로써, 원래의 dp도 필요 없어지며 for문도 하나가 감축된다. 해당하는 코드는 아래와 같다.

 

import sys
input = sys.stdin.readline


if __name__ == '__main__':
    N, K = map(int, input().split())
    dp = [0]*(K+1)

    for _ in range(N):
        w, v = map(int, input().split())

        for i in range(K, w-1, -1):
            dp[i] = max(dp[i], v + dp[i-w])

    print(dp[K])