[#15486] 퇴사2

문제

#15486 퇴사2
Gold5
적용 알고리즘: 동적 계획법 알고리즘

---

풀이 방법

• 뒤에서부터 접근한다. 매 날짜마다 최고의 이익을 선택한다.
• 날짜는 1일부터 시작하므로 편의를 위해 인덱스도 첫째날을 1로 지정한다.
• 현재 날짜에서 시작 할 수 있는 일이 끝나는 날짜가 퇴사하는 날을 넘어서면 해당 일은 시작 할 수 없다.
• 현재 날짜에서 시작 할 수 있는 일이 끝나는 날짜가 퇴사하는 날을 넘어서지 않으면 해당 일은 시작할 수 있다.
• max(“현재 날짜의 가치”, “본인 날짜의 일의 가치” + “본인 날짜 + 본인날짜에 시작하는 일을 더한 날짜의 가치”)

[7 + 2 > 8] dp[7] = dp[8]
[6 + 4 > 8] dp[6] = dp[7]
[5 + 2 < 8] dp[5] = 15 + dp[5 + 2] = 15 or dp[5] = dp[6]
[4 + 1 < 8] dp[4] = 20 + dp[4 + 1] = 20 + 15 = 35 or dp[4] = dp[5]

코드 흐름

1. 사용자의 입력을 정리한다. 편의상 첫째 날을 1번 인덱스로 두기 위해 0번째 인덱스에 [0, 0]을 넣어준다.
2. 루프를 n번째 날부터 1번째 날까지 돌린다.
3. 만약 “현재 날짜” + “현재 날짜에서 시작할 수 있는 일의 소요 일수”가 퇴사 일을 넘어가면 해당 일은 시작 할 수가 없다(가치 변동 x). 따라서 현재 날짜 + 1일의 가치가 현재 가치가 된다.
4. 3번의 나머지 경우(퇴사 일을 넘기지 않을 때), “현재 날짜 + 1일의 가치”와 “현재 날짜의 가치” + “현재 날짜 + 현재 날짜에서 시작하는일의 소요 일을 더한 날의 (계산된) 가치”중 더 큰 값이 현재 날짜에서의 최대 가치가 된다.
5. 첫째 날의 값을 출력한다.

코드

import sys 


input = sys.stdin.readline

n = int(input())
data = []
data.append([0, 0])
for i in range(n):
    data.append([int(m) for m in input().split()])

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

print(dp[1])

체감 난이도: 4.8/5
진짜 동적 프로그래밍 너무 어려운거 아니냐… 이전 문제로 나름 감 잡았다고 생각했는데 난이도 어려운 문제 풀어보니까 다시 감이 안잡힌다. 점화식 세우기조차 너무 어려운데…? 그리고 진짜 문제 접근 방법이 너무 어려운거 같다. 처음에는 1부터 시작할 줄 알았는데 조금 인터넷 참고했는데 뒤에서 문제를 진행하네… 진짜 너무 어렵다. 그리고 이런문제는 인덱스가 너무 어려움… 헷갈려. 많이 풀어보는게 답이다…