[ BOJ 14728 ] 벼락치기(Python)

uoayop·2021년 5월 27일
0

알고리즘 문제

목록 보기
74/103
post-thumbnail

문제

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

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

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


문제 풀이

  1. 입력 받기
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시간 동안 공부했을 때 얻을 수 있는 최대 점수

  1. 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])
profile
slow and steady wins the race 🐢

0개의 댓글