백준 15486 퇴사 2 풀이/코드 (파이썬) 다이나믹 프로그래밍

코드 복사해보실 분은 깃허브링크 눌러주세요!

GitHub - Rhyankwon/algorithms

문제 설명

문제 해결 논리

1. 입력받는 값의 갯수가 N개라고 할때 N번째부터 시작한다.
2. 뒤에서부터 매번의 최대값을 갱신하는데, 임의의 시점을 n이라 하고 그때 걸리는 시간을 t라고 하면 n에서의 최대값은 [n+1 값(바로 직전값)]과 [n+t 값(t시간 전의 값) + 현재값]을 비교한 최대값이다.
3. 0일째까지 2를 반복해서 0일째에 나오는 값을 출력 후 끝낸다.

간단히 얘기하자면, 만약 t번째 전 값과 현재 값을 더한 것보다 이전 값이 더 크면 현재 값을 무시하고 그냥 이전 값을 현재값으로 하는게 문제의 포인트이다.

나는 처음에 아이디어는 금방 냈는데, 만약 (지금 할당된 시간값+현재위치)값이 전체 길이를 넘어서는 경우에는 반드시 그냥 직전 값을 가져오도록 하는 과정을 깜박해서 조금 헤맸다. 다이나믹 프로그래밍의 정석같은 문제이다.

값이 워낙 크다보니 3000ms이상의 결과가 나온다.