[DP] (1) 퇴사

이코테 p.377 퇴사

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

14501번: 퇴사

문제 해설 및 소스코드

• 첫날이 아닌, 마지막날부터 계산해야 함
• dp[i] = i번째 날 부터 퇴사 전까지 벌 수 있는 최대 비용
• 점화식은 다음과 같음
  • dp[i] = max(p[i] + dp[t[i] + i], max_cost)
  • i번째 날의 비용과 i번째 날의 상담이 끝나는 날의 최대 비용을 합친 것 vs 현재까지의 최대 비용을 비교하여 더 큰 값 선택

# dp[i] = i번째 날부터 퇴사일까지 벌 수 있는 최대 비용
# 점화식: dp[i] = max(p[i] + dp[i + t[i]], max_value)

# 입력 받기
n = int(input())
t = [] # 시간 리스트
p = [] # 비용 리스트
for _ in range(n):
  a, b = map(int, input().split())
  t.append(a)
  p.append(b)

dp = [0] * (n + 1)

max_cost = 0 # 최대 수익
# 마지막 날부터 거꾸로 계산
for i in range(n - 1, -1, -1):
  end_time = t[i] + i # i번째 날의 상담이 끝나는 날짜
  if end_time <= n: # 퇴사일 전에 상담이 끝나는 경우
    dp[i] = max(p[i] + dp[end_time], max_cost)
    max_cost = dp[i]
  else: # 퇴사일 전에 상담이 끝나지 않는 경우
    dp[i] = max_cost

print(max_cost)