[백준] 14728번 벼락치기 파이썬

문제링크: https://www.acmicpc.net/problem/14728

난이도: GOLID V

문제해결 아이디어

• dp배열 모양을 단원 x 시간으로 설정
• 현재 단원을 학습할지 말지를
• 이전 단원의 현재 시간 값과 이전단원의 현재시간 - 현재단원을 학습하는 시간 비교

소스코드

import sys

input = sys.stdin.readline

n,t = map(int, input().split())
time = []
score = []

for _ in range(n):
    a,b = map(int, input().split())
    time.append(a)
    score.append(b)

dp = [[0] * (t+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, t+1):
        if j >= time[i]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-time[i]] + score[i]) 
        else:
            dp[i][j] = dp[i-1][j]

print(max(dp[-1]))