[자바] 백준 14501 문제 풀이 - 퇴사

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

14501번: 퇴사

 

마지막날까지 최대로 일할 때 얻을 수 있는 최고 수익을 구하는 문제.

처음에는 그리디인가 싶어서 그리디로 풀려고했지만, 결국 이건 답이 있는 문제기 때문에 다이나믹 프로그래밍으로 풀었다.

 

해법은 일단 일을 하기 시작하면 그 소요 기간만큼은 일할 수 없다는걸 가정하는것.

 

0. 퇴사날 이후로는 일을 할 수 없기 때문에 그 날에 걸리는 일들은 전부 -987654321로 처리했다.

1. 일 수를 돌면서

2. 그날 일을 한다면 소요기간만큼 건너 뛰고 그 다음 날부터 모든 일에 일을 할 수 있으므로 그날 일했을때 얻을수 있는 비용과 비교해서 최대의 일을 한 것으로 대체한다.

 

https://github.com/mychum1/shelf/blob/master/com.ksko.algorithm/src.main.java/baekjoon/P_14501.java

mychum1/shelf