[ BOJ 14728 ] 벼락치기(Python)

문제

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

한 문제를 맞기 위해선 특정 시간 이상 공부를 해야할 때,
주어진 시간 안에 얻을 수 있는 최대 점수를 구하면 된다.

인덱스 에러때매 돌아버릴뻔~~

문제 풀이

0. 입력 받기

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

times, scores = [0], [0]

for _ in range(N):
    t, s = map(int, input().rsplit())
    times.append(t)
    scores.append(s)

과목을 공부할 때 소요되는 시간과 얻을 수 있는 점수를 각각 입력 받았다.

1. dp 배열 정의하기

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

dp[i][j] = i개의 단원 중 j시간 동안 공부했을 때 얻을 수 있는 최대 점수

2. times[i] 에 따라 dp 값 할당해주기

for i in range(1, N+1):
    for j in range(1, T+1):
    	# j가 현재 과목을 공부할 때 드는 시간보다 크거나 같으면
        # 현재 과목을 공부할 시간이 있다는 뜻이므로
        # (현재 과목 공부 X, 현재 과목 공부 O) 시간을 비교해준다.
        if j >= times[i]:
            dp[i][j] = max( dp[i-1][j], 
                            dp[i-1][j-times[i]] + scores[i] )
        # j가 현재 과목을 공부할 시간보다 작으면
        # 현재 과목을 공부할 수 없으므로 이전 시간을 할당해준다.
        else:
            dp[i][j] = dp[i-1][j]

코드

import sys
input = sys.stdin.readline

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

times, scores = [0], [0]

for _ in range(N):
    t, s = map(int, input().rsplit())
    times.append(t)
    scores.append(s)

# i개의 단원을 j시간 동안 공부했을 때 얻을 수 있는 최대 점수
dp = [[0 for _ in range(T+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, T+1):
        if j >= times[i]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-times[i]] + scores[i])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][T])