[백준/python] 14501 - 퇴사

14501번: 퇴사

n = int(input())
sch = [
    tuple(map(int, input().split()))
    for _ in range(n)
]
dp = [0] * 16

if sch[n - 1][0] == 1:
    dp[n - 1] = sch[n - 1][1]
else:
    dp[n - 1] = 0

for i in range(n - 2, -1, -1):
    if i + sch[i][0]> n:
        dp[i] = dp[i + 1]
    else:
        dp[i] = max(dp[i + 1], sch[i][1] + dp[i + sch[i][0]])

print(dp[0])

알고리즘:

dp를 뒤에서부터 갱신해 주는 것이 포인트.

dp를 모두 0으로 초기화 한 후, 스케쥴의 가장 마지막 날이 1인 경우에는 dp의 마지막은 마지막 날의 보수가 되고, 그렇지 않으면 일을 완료하지 못한 채 퇴사를 하기 때문에 0으로 초기화

dp[n - 2] 부터는 뒤에서 부터 차례대로 dp값을 넣어주는데, 만약에 현재 i 값, 즉 주소값 + 스케쥴의 날이 퇴사 일을 넘어버리면 뒤에 있는 dp 값을 dp[i]로 갱신해준다. 

주소 값 + 스케쥴 날이 퇴사 일보다 적거나 같다면 그 전의 dp값과 해당 스케쥴의 보수 + 일을 하지 못하는 범위 바로 전의 보수 중 큰 값을 dp[i]로 넣어준다.

만약에 테케가 이렇게 있다면

10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 30, 30, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 40, 30, 30, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 50, 40, 30, 30, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 60, 50, 40, 30, 30, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 70, 60, 50, 40, 30, 30, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 80, 70, 60, 50, 40, 30, 30, 0, 0, 0, 0, 0, 0, 0, 0]

이런 식으로 dp가 갱신된다.

---

고민을 정말 많이 한 문제. 거꾸로 탐색하면 이렇게 간단한 것을 ... 이런 식으로 최대 값을 갱신할 때 역순으로 for문을 돌리는 발상을 떠올리도록 머리 속에 잘 입력해놔야겠다.

 

혹시 까먹을 까봐 for 문 역순 예시)