백준 | 퇴사

백준 퇴사

어떤 상담원이 N + 1일째 되는 날 퇴사를 하는데, 남은 N일 동안 최대한 많은 상담을 하고 싶어 한다고 한다.

N일 동안 매일 상담이 잡혀 있고, 각 상담은 완료하는 데 걸리는 기간 T와 상담을 완료했을 때 받을 수 있는 금액 P가 존재한다.

이러한 상황에서 몇 개의 상담을 적절히 골라 상담원이 얻을 수 있는 최대 수익을 구하는 문제이다.

이 문제에서 생각해야 할 부분은 퇴사 전에 진행할 수 있는 상담 중에서 단일 금액이 큰 상담을 진행하는 게 무조건 좋은 건 아니라는 것이다.

오히려 더 적은 금액의 상담을 여러 개 진행하는 게 결과적으론 더 큰 수익을 낼 수도 있다는 말이다.

그래서 dp[i]를 i일까지 일해서 벌 수 있는 최대 수익으로 정의하고, DP로 접근했다.

구체적으로는 퇴사 전(N일째)까지 끝낼 수 있는 상담만 고려하기 위해 dp를 0 n + 1개로 초기화했다.

그리고 1일부터 n일까지 당일에 신청 받은 상담의 t(소요 기간)와 p(수익)을 받아서, 먼저 퇴사 전까지 끝낼 수 있는 일인지를 따졌다.

가능하다면, '어떤 경우에 의해 이미 업데이트된 dp[end_date]'와 '어제까지의 최대 수익 dp[i - 1]에 오늘부터 새로운 상담을 t 동안 진행하여 얻을 수 있는 수익 p를 더한 값' 중 큰 값을 dp[end_date]에 저장했다.

그리고 오늘 진행할 수 있는 상담을 진행하느냐, 진행하지 않느냐와는 별개로..

'이미 업데이트된 어제까지의 상담 최대 수익'이 '오늘까지의 수익'보다 크다면, 상담원은 오늘을 쉬고 어제까지의 최대 수익을 그대로 물려받으면 된다.

따라서 이 비교를 매일 진행(매 반복마다 진행)하여 필요하다면 dp[i] 값을 dp[i - 1]로 업데이트해준다. (문제의 예제 입력 4를 직접 돌려보면 알 수 있다!)

코드(정답)는 다음과 같다.

import sys


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

# 배열 초기화
# dp[i]: i일째의 최대 수익
dp = [0 for _ in range(n + 1)]

for i in range(1, n + 1):
    t, p = map(int, sys.stdin.readline().split())

    # i일에서 (t, p)짜리 상담을 진행할 것인가?
    end_date = i + t - 1
    # 퇴사 전에 상담을 끝낼 수 있는 경우만 (t, p)짜리 상담 진행
    if end_date <= n:
        """
        (1) 다른 경우에 의해 만들어질 수 있는 dp[end_date]
        (2) (i - 1)일까지의 최대 수익 dp[i - 1]에 i일에 시작할 상담 수익 p를 더한 값

        위의 두 값 중 큰 값을 dp[end_date]으로 업데이트!
        """
        dp[end_date] = max(dp[end_date], dp[i - 1] + p)
    
    """
    i일에 상담을 진행하지 않았을 때, (i - 1)일까지의 상담 수익이 더 클 수 있다.
    매일 dp[i], dp[i - 1]을 비교하여 만약 전날까지의 수익이 더 크다면, 그대로 물려받는다.
    """
    if dp[i] < dp[i - 1]:
        dp[i] = dp[i - 1]

# print(dp)
print(max(dp))