14728 : 벼락치기 Python

14728 : 벼락치기

배낭문제로 풀 수 있는 문제인데 배낭문제를 풀 때마다 헷갈리는 부분이 있어 기록으로 남기려고 한다.

for j in range(time, T + 1):
    dp[i][j] = max(dp[i - 1][j - time] + score, dp[i - 1][j])

이 부분의 max(dp[i - 1][j - time] + score, dp[i- 1][j])를 매번 max(dp[i - 1][j - time] + score, dp[i][j]로 작성해서 틀리는 일이 잦았다.

 

비교의 목적을 제대로 상기할 필요가 있다. 만약 내가 헷갈렸던 코드 그대로 사용하게 되면 현재 선택된 물건을 가방에 넣는 것과 넣지 않는 것을 비교하는 것이기 때문에 무조건 물건을 넣는 쪽이 가치가 더 높다. 하지만, 현재 선택된 물건과 무게가 같은데 더 가치가 높은 물건이 있다면 어떻게 될까?

 

이 경우에는 가치가 더 높은 물건이 먼저 등장하느냐 이후에 등장하느냐의 문제가 된다. 만약 5의 무게를 갖는 물건 A, B가 있고 각각의 가치가 6, 4라고 하자. A의 물건이 먼저 등장했으므로 첫 번째 물건까지 확인한 가치의 최대치는 6이지만, 두 번째 물건까지 확인한 최대 가치는 4가 된다.

 

왜? max(dp[i - 1][j - weight] + value, dp[i][j])이기 때문에 현재 물건을 넣느냐 빼느냐만 고려하기 때문이다. 그렇기 때문에 반드시 dp[i - 1][j] 즉, 이전 물건까지 확인했을 때 해당 무게에서 얻을 수 있는 최대 가치와 현재 물건을 넣었을 때 얻을 수 있는 최대 가치와 비교해야 한다.

 

 

그러므로 max(dp[i - 1][j - time] + score, dp[i- 1][j])와 같이 작성해야 한다.

전체 코드

import sys

# print = sys.stdout.write
input = sys.stdin.readline
# f = open("input.txt", "rt")
# input = f.readline

N, T = map(int, input().split())

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


def main():
    for i in range(1, N + 1):
        time, score = map(int, input().split())
        dp[i][:time] = dp[i - 1][:time]
        for j in range(time, T + 1):
            dp[i][j] = max(dp[i - 1][j - time] + score, dp[i - 1][j])

    print(dp[N][T])


if __name__ == "__main__":
    main()