[dp] 백준 12865 평범한 배낭/ 14728 벼락치기

두 문제 모두 "평범한 배낭" 문제와 같다. 

 

변수명만 다르게 하면 될 뿐, 코드까지 똑같은 문제이다.

 

import sys
N, T = map(int, sys.stdin.readline().split())

time_score = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [[0]*(T+1) for _ in range(N+1)]

for y in range(1, N+1):
    time = time_score[y-1][0]
    score = time_score[y-1][1]
    for x in range(1, T+1):
        if time<=x:
            dp[y][x]=max(dp[y-1][x-time]+score, dp[y-1][x])
        else:
            
            dp[y][x]=dp[y-1][x]
print(dp[-1][-1])

 

dp[y][x] = y개 단원까지 있고, 총 공부시간이 x라고 할 때 맞을 수 있는 최대 점수