코드

n = int(input())
t = []
p = []

for _ in range(n):
    x, y = map(int, input().split())
    t.append(x)
    p.append(y)
    
def max_earn(n, t, p):
    # dp 테이블 초기화
    # dp[i] => i일까지 얻은 최대 이익
    dp = [0] * (n+1)

    # 최대 수익
    max_earning = 0

    # 뒤집어서 문제 풀기
    for i in range(n-1, -1, -1):

        # 총 소요 일수
        # i => 오늘의 날짜
        # t[i] => i날 있는 상담의 소요 일수
        tot = t[i] + i

        # 총 소요 일수가 남은 근무 일  보다 작다
        #   => 퇴사 전에 상담을 모두 완료할 수 있는 경우
        if tot <= n:
            
            # tot일까지 얻은 최대 이익 + i(오늘) 얻은 최대 이익과 다른 날 기준의 최대 이익을 비교
            # 더 큰 값을 해당 날(i)의 최대 이익으로 바꿈
            dp[i] = max((dp[tot] + p[i]), max_earning)
            
            # 최대 이익도 위의 값으로 업데이트
            max_earning = dp[i]
            
        # 그렇지 않은 경우
        else:
            # 최대 이익은 기존의 값이 더 크므로 기존 값을 dp에 업데이트
            dp[i] = max_earning

    print(max(dp))    

max_earn(n, t, p)

문제 해설

DP 문제.

이러한 제한적인 시간 동안 최대 이익을 낼 수 있는 문제의 경우, 편하게 그냥 뒤에서부터 경우를 하나씩 따져가면서 문제를 푸는 것이 유용한 방법이 될 수 있다.

일단 1차적으로 마지막 날에서부터 내려오면서 그날의 상담을 진행하는 경우 퇴사 전까지 상담을 마무리할 수 있는지 따져보고 마무리가 가능하다면?

전까지 최대로 벌어들인 수익 vs 새롭게 진행한 상담으로 창출한 수익 + 그 후에 벌어들일 수익

위의 경우를 비교하여 더 큰 값을 DP 테이블에 업데이트 시킨다.

최종적으로 완성된 DP 테이블 중 가장 큰 값을 출력하면 정답이다.

댓글남기기

참고