이해

• N일 동안 하루에 하나씩 서로 다른 상담이 잡혀있다.
• 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
• 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.
• N+1일째 되는 날에 퇴사를 하기 때문에 상담이 완료되는 날이 N일을 넘어가면 상담을 할 수 없다.
• 상담을 적절히 했을 때, 얻을 수 있는 최대 수익을 출력하라.

계획

• dynamic programming 유형으로 접근, 점화식은 다음 아래와 같다.

  dp[i]: i일부터 상담을 시작할 때 얻을 수 있는 최대 수익
  dp[i] = max(dp[i+1], Pi + dp[i + Ti]) if i + Ti <= N + 1 else dp[i+1]
  i = N, N-1, N-2, ..., 1 dp 테이블 업데이트
  

실행

n = int(input())
t = [0] * (n + 1)
p = [0] * (n + 1)
dp = [0] * (n + 2)

for i in range(1, n + 1):
    t[i], p[i] = map(int, input().split())

for i in range(n, 0, -1):
    dp[i] = max(dp[i + 1], p[i] + dp[i + t[i]]) if i + t[i] <= n + 1 else dp[i + 1]

print(dp[1])

개선

• 딱히 없다.

회고

• 예전에 푼 문제였어서 바로 유형을 캐치하여 쉽게 풀었다.