14501번
-
백준 14501번 퇴사 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 4. 21. 11:14
이 글은 백준 알고리즘 문제 14501번 "퇴사" 를 풀이한다.삼성 SW 역량 테스트의 기출 문제이다.동적계획법을 통해 문제를 해결할 수 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일Ti3511242Pi1020102015402001일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.또한, N+1일 째에는 ..