백준: 15486 퇴사 2

문제

15486번: 퇴사 2

 

문제 풀이

 기존에 풀었던 퇴사 문제에서 N의 범위가 커진 문제이다. N의 범위가 커짐에 따라 DFS로 풀지 않고 DP로 풀어야 문제를 해결할 수 있다. 즉 최대 수익을 완전 탐색을 통해 찾지 않고, 메모이제이션을 통해 값을 누적시켜가며 N일 까지 진행시켜야 한다.

 

 점화식은 현재 날짜 + 일하는데 필요한 날짜 <= N인 경우에, 해당 일자의 수익이 기존의 값과 비교하여 일을 하는 것이 이득인지를 계산해 주면 된다

 

코드

from sys import stdin


if __name__ == "__main__":
    n = int(stdin.readline())
    dp = [0] * (n + 1)
    schedule = [list(map(int, stdin.readline().split())) for _ in range(n)]

    for cur_day in range(n):
        spend_day, pay = schedule[cur_day]
        if cur_day + spend_day <= n:
            dp[cur_day + spend_day] = \
                max(dp[cur_day + spend_day], dp[cur_day] + pay)

        dp[cur_day + 1] = max(dp[cur_day + 1], dp[cur_day])

    print(dp[n])

 `dp[n]`에 최대 수익을 반영하기 위해, `dp[cur_day + 1] = max(dp[cur_day + 1], dp[cur_day])`가 필요하다.