[백준 Python] 14728번 벼락치기

백준 파이썬 14728번 벼락치기

Gold 5

 

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

n, t = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)] #공부시간, 배점
dp = [0]*(t+1)
for time, score in lst:
    for i in range(t, time-1, -1):
        dp[i] = max(dp[i], dp[i-time]+score)
print(dp[t])

 

냅색 유형의 문제로 dp를 사용해서 얻을 수 있는 최대점수를 구해주면 된다.

다음 문제와 거의 똑같다!

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