[백준] 14501 퇴사 .py

www.acmicpc.net/problem/14501

14501번: 퇴사

n = int(input())
data = []
for _ in range(n):
    days, cost = input().split(" ")
    data.append((int(days), int(cost)))
    
dp = [0] * n

if data[-1][0] == 1:
    dp[-1] = data[-1][1] # 마지막 날짜는 먼저 처리
    
for i in range(n-2, -1, -1):
    days, cost = data[i][0], data[i][1]
    if days + i < n:
        dp[i] = max(dp[i + days] + cost, dp[i+1])
    elif days + i == n:
        dp[i] = max(cost, dp[i+1])
        
    else:
        dp[i] = dp[i+1]

print(dp[0])

 

# 1. days + i 가 n 보다 작은경우:

max(오늘 상담이 종료하는 시점의 dp최대값 + 오늘날짜의 상담비용, 내일부터 전체 상담 종료시점까지의 최대 상담비용)

 

# 2. days + i 가 n인경우:

i + 1 > n 이므로 IndexError.

max(오늘 상담 비용, 내일부터 전체 상담 종료시점까지의 최대 상담비용)

 

# 3. days+ i 가 n 보다 큰 경우:

해당 날짜는 상담을 할 수 없으므로 dp[i+1] 값이 현재까지 최대값이다.