[Python] BOJ(백준) 14501번 - 퇴사

링크

https://www.acmicpc.net/problem/14501

난이도(solved.ac 참고)

실버4

풀이

동적계획법은 알고리즘 수업때 풀어본 게 마지막이니까, 대충 2-3달만에 풀어봤는데 역시 쉽지 않다. 실버 4였지만.. 생각하는 힘이 좀 부족하다고 생각한다. 동적계획법 문제는 많이 풀어봐야겠다.

 

dp를 100이나 둔 이유는 16(n의 최대값 + 1)으로 넣어서 했더니 자꾸 인덱스 오류가 나서 짜증나서 그냥 100으로 해버렸다. 물론 메모리 제한이 좀 있었다면 당연히 못 맞았다.

 

dp 배열에 대해 i일 뒤에 받게 될 금액, 그러니까 dp[i] + p_list[i]가 현재 금액 (dp[i+t_list[i]])보다 크다면 큰 값을 반영해주는 방식으로 진행했다.

 

그리고, 현재 받게 될 금액이 다음날 받게 될 금액보다 크다면 다음날 받게 되는 금액 또한 현재 받는 금액으로 바꿔준다.