[백준 14501 파이썬] 퇴사

일단 해볼게·2023년 5월 5일
0

백준

목록 보기
123/132

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

import sys
input = sys.stdin.readline

n = int(input().rstrip())
consultings = [list(map(int, input().rstrip().split())) for _ in range(n)]
dp = [0] * (n + 1)

for i in range(1, n + 1):
    t, p = consultings[i - 1][0], consultings[i - 1][1]

    if i + t - 1 <= n: # i + t - 1 = i일째에 시작한 상담이 끝나는 날
        dp[i + t - 1] = max(dp[i + t - 1], dp[i - 1] + p) # 현재 값과 추가 상담을 한 값을 비교

    if dp[i] < dp[i - 1]:
        dp[i] = dp[i - 1]

print(max(dp))

i일째에 시작한 상담이 끝나는 날(i+t-1)을 기준으로 i-1일째까지의 최대 상담 비용(dp[i-1])에 이번 상담 비용(p)를 더한 값들 중 가장 큰 값으로 DP테이블(dp)을 계속 갱신한다.

profile
시도하고 More Do하는 백엔드 개발자입니다.

0개의 댓글