[Python] 퇴사

문제

14501번: 퇴사

입력

• 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
• 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

• 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

입력 예제

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

출력 예제

45

55

문제 풀이

• 다음 상담이 가능한 날은 오늘 날짜 + 상담에 소요되는 날이다.
• 따라서 최대 수익은 이번 상담으로 받는 돈 + 다음 상담 가능한 날짜 부터의 최대 수익이다.
• 이 점을 이용하여 뒤에서부터 차례대로 계산하면 답을 도출할 수 있다.
• 점화식은 아래와 같다.

# max_value는 뒤에서부터 계산 할 떄 현재까지의 최대 수익
dp[i] = max(p[i] + dp[t[i] + i], max_value)

 

코드

n = int(input())
# 시간, 수익
t, p = [], []
dp = [0] * (n + 1)
max_val = 0
for _ in range(n):
    x, y = map(int,input().split())
    t.append(x)
    p.append(y)
# 뒤에서 부터 확인하면서 최대 수익 갱신
for i in range(n - 1, -1, -1):
    # 다음 상담 시작할 수 있는 날
    time = i + t[i]
    # 최대 상담 가능 날짜가 n - 1이므로, 다음상담 가능 날짜는 n까지 일 때 조건 성립
    if time <= n:
        # 최대 수익은 현재 수익 + 다음 상담일부터의 최대 수익
        dp[i] = max(p[i] + dp[time], max_val)
        max_val = dp[i]
    else:
        dp[i] = max_val
print(max(dp))