[DP] 백준 15486번 “퇴사 2” Python 풀이

문제 링크

• https://www.acmicpc.net/problem/15486

풀이

• 예제 입력이 아래와 같다고 가정해봅시다.

            1일    2일   3일    4일   5일    6일    7일
      Ti     3     5     1     1     2     4      2
      Pi    10    20    10    20    15    40    200

• 만약, 1일차에 상담을 진행한다면, 해당 상담은 3일동안 진행되며, 4일차부터 다시 상담을 진행할 수 있습니다.

• 따라서, 1일차에 상담을 진행할 경우의 최대 이익은,

• ‘1일 차의 상담 금액 + 4일부터의 최대 상담 금액’이 됩니다.

• 이러한 원리를 뒤쪽 날짜부터 적용함으로써 문제를 해결할 수 있습니다.

• 뒤쪽 날짜부터, 매 상담에 대하여 ‘현재 상담 일자의 이윤(p[i]) + 현재 상담을 마친 일자부터의 최대 이윤(dp[t[i] + i]])’을 계산하면 됩니다.

• 이후, 계산된 값들 중 최댓값을 출력하면 됩니다.

• dp[i]가 ‘i번째 날부터 마지막 날까지 낼 수 있는 최대 이익’이라고 한다면, 점화식은 아래와 같습니다.

      dp[i] = max(p[i] + dp[t[i] + i], max_value)

  • 이때 max_value는, ‘i번째 날부터 마지막 날까지 낼 수 있는 최대 이익’을 의미하게 됩니다.

• 결과적으로, 예제 입력에 따른 DP 테이블은 아래와 같이 완성됩니다.

  • [45, 45, 45, 35, 15, 0, 0, 0]

코드

import sys

n = int(sys.stdin.readline())

t = [] # 각 상담을 완료하는데 걸리는 기간
p = [] # 각 상담을 완료했을 때 받을 수 있는 금액

# i번째 날부터 마지막 날까지 낼 수 있는 최대 이익
dp = [0] * (n+1)

for _ in range(n):

    # 날짜별 상담 완료 기간 및 상담 완료 금액 저장
    x, y = map(int, sys.stdin.readline().split(" "))
    t.append(x)
    p.append(y)

# i번째 날부터 마지막 날까지 낼 수 있는 최대 이익
max_value = 0

# 마지막 날짜부터 역순으로 탐색
for i in range(n-1, -1, -1):

    # 해당 날짜에 상담을 진행할 수 있다면
    if (i + t[i] <= n):

        # [현재 상담 일자의 이윤 + 현재 상담을 마친 일자부터의 최대 이윤]과
        # 현재 날짜부터 마지막 날까지 낼 수 있는 최대 금액을 비교
        dp[i] = max(p[i] + dp[i + t[i]], max_value)
        max_value = dp[i]

    # 해당 날짜에 상담을 진행할 수 없다면
    else:
        dp[i] = max_value

print(max_value)