[python] 백준 15486 : 퇴사 2

문제 링크
https://www.acmicpc.net/problem/15486

접근

대충 봐도 dp 문제라는 것을 알 수 있다.
우선 N이 150만까지이므로 O(N)이나 O(NlogN)의 복잡도를 가진 알고리즘을 생각해볼 수 있다.

어차피 최댓값만 구하면 되는 문제이므로 주어진 일 수에 해당하는 최대 이익을 반복적으로 구하면 된다고 생각하였다. 따라서 DP로 풀어야 겠다고 생각했다.

풀이

풀이의 핵심은 해당 일까지 얻을 수 있는 최대 이익이다.

1일까지 밖에 없을 때의 최댓값
2일까지 밖에 없을 때의 최댓값
3일까지 밖에 없을 때의 최댓값
...
N일까지의 최댓값

이런식으로 계속 나아가다 보면 결국 총 주어진 일 수인 N일까지 얻을 수 있는 이익의 최댓값을 구할 수 있다.

우선 주어진 예시의 1일차 부터 보자

1일차에 얻을 수 있는 이익은 0이다. 1일차에 해당하는 일을 잡아도 시간이 3일 소요되기 때문에 얻을 수 있는 이익이 없다. 다만 이 일을 선택하였을 때 3일까지의 최대 이익이 10이 될 가능성이 생긴다.
dp = [0, 0, 0, 10, 0, 0, 0, 0] (<-- 편의상 0일차도 넣었음)

2일차에도 역시 얻을 수 있는 이익은 0이다. 그 전 날에 얻을 수 있는 이익도 없고 2일차에 잡은 일도 5일이라는 시간이 소요되기 때문이다. 다만 5일까지의 최대 이익이 20이 될 가능성이 생긴다.
dp = [0, 0, 0, 10, 0, 0, 20, 0]

3일차에는 얻을 수 있는 이익이 10이다. 이 10은 1일차에 한 일이 완료된 10이라고 볼 수 있고, 3일차에 한 일의 이익이라고 볼 수 있다. 하지만 어떠한 경우든 3일차까지 얻을 수 있는 최대 이익은 10이다.
dp = [0, 0, 0, 10, 0, 0, 20, 0]

4일차에는 얻을 수 있는 이익이 30이다. 왜냐하면 3일차까지 얻을 수 있는 최대 이익이 10이고, 4일차에 해당하는 일이 하루만에 20 이익을 벌어다주기 때문이다.
dp = [0, 0, 0, 10, 30, 0, 20, 0]

5일차에는 얻을 수 있는 이익은 아직 30이다. 왜냐하면 4일차까지 얻을 수 있는 최대 이익이 30이고, 5일차에 해당하는 일이 이틀이 소요되기 때문이다. 대신 6일까지의 최대 이익이 45일이 될 가능성이 생긴다.
dp = [0, 0, 0, 10, 30, 30, 45, 0]

6일차에는 얻을 수 있는 이익은 45이다. 5일차에 해당하는 일이 끝났기 때문이다. 대신 6일까지의 최대 이익이 45일이 될 가능성이 생긴다.
6일차부터는 남은 시간이 없어 더이상 추가적으로 일을 하지 못한다. 그래서 더이상 추가되는 이익은 없다. 여기서 답인 45가 도출된다
dp = [0, 0, 0, 10, 30, 30, 45, 0]
하지만 6일차에서 조금 더 생각을 해보자. 만약 일 수가 조금 더 있었더라면 어떻게 되었을까? 예를들어 7일이 아닌 9일이 있었다면, 6일까지 일을 할 수 있다. 그렇다면 5일차의 일을 하는 것이 과연 최대 이익을 뽑아낼 수 있을까? 생각을 해볼 필요가 있다. 뒤에 있는 7일째의 일을 배제한다면 5일차에 이틀이 걸리는 일을 하지 않고 6일차에 해당 일을 하는 것이 더 큰 이익을 가져온다.

5일차 일을 맡은 경우: 6일차 일을 못 하므로 최대 이익 30+15=45
5일차 일을 맡지 않은 경우: 6일차 일을 할 수 있으므로 최대 이익 30+40=70

• 단 9일 이상 있고, 7일차의 일을 생각하지 않는다.

이를 통해 우리는 다음과 같은 코드를 생각할 수 있다.

dp = [0 for _ in range(n + 1)]

for i in range(1, n + 1):
    dp[i] = max(dp[i], dp[i - 1])  # 이전까지의 최댓값
    fin_date = i + t[i] - 1  # 당일 포함
    if fin_date <= n:  # 최종일 안에 일이 끝나는 경우
        # i일부터는 일을 해야하므로 i일에 얻을 수 있는 최댓값이 아닌 i-1일까지 얻을 수 있는 최댓값을 구한다
        dp[fin_date] = max(dp[fin_date], dp[i - 1] + p[i])

i는 1부터 시작한다.
1일부터 차례대로 탐색하며 진행한다.

i일에 얻을 수 있는 이익은 그 전날 얻을 수 있는 이익보다는 크거나 같을 것이므로 dp[i] = max(dp[i], dp[i - 1])를 해준다

i일에 해당하는 일이 끝나는 시점인 fin_date = i + t[i] - 1를 정의하였고, fin_date가 최종일 이하면 i일에 일을 할 수 있으므로 fin_date일에 영향을 준다.
따라서 dp[fin_date] = max(dp[fin_date], dp[i - 1] + p[i])

정답코드

import sys

input = lambda: sys.stdin.readline().rstrip()

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

dp = [0 for _ in range(n + 1)]

for i in range(1, n + 1):
    dp[i] = max(dp[i], dp[i - 1])  # 이전까지의 최댓값
    fin_date = i + t[i] - 1  # 당일 포함
    if fin_date <= n:  # 최종일 안에 일이 끝나는 경우
        # i일부터는 일을 해야하므로 i일에 얻을 수 있는 최댓값이 아닌 i-1일까지 얻을 수 있는 최댓값을 구한다
        dp[fin_date] = max(dp[fin_date], dp[i - 1] + p[i])
print(max(dp))