[백준 15401번] 퇴사

난이도: 실버 4

문제 링크: www.acmicpc.net/problem/14501

출처: 삼성전자 SW 역량 테스트

14501번: 퇴사

백준 14501번 문제 퇴사

다이나믹 프로그래밍을 이용하는 문제입니다.

지금까지 누적 얻은 이익을 매번 다시 계산하지 않고, 이전에 계산해서 저장해 놨던 값을 꺼내어 이용하면 됩니다.

 

이런 문제는 뒤에서부터 접근하면 보다 쉽게 풀 수 있습니다.

위 사진에 있는 예시를 기준으로 설명하겠습니다.

 

N+1일 후에 퇴사를 합니다. 따라서 N일까지 일할 수 있는지 여부를 우선 체크해야 합니다. 주의할 점은 7일차에 하루가 걸리는 상담을 할 경우 7 + 1 = 8이지만, 상담을 할 수 있다는 점입니다. 따라서 x일차 + y일 걸릴 때, x + y <= 8이면 상담을 진행할 수 있습니다.

7일차에 있는 상담은 이틀이 걸리므로, 7 + 2 = 9입니다. 따라서 진행할 수 없습니다.

6일차에 있는 상담은 나흘이 걸리므로, 6 + 4 = 10입니다. 따라서 진행할 수 없습니다.

5일차에 있는 상담은 이틀이 걸리므로, 5 + 2 = 7입니다. 따라서 진행할 수 있습니다.

이 때 dp[5]에 적히는 값은, p[5] + 지금까지 이미 일한 dp값과, 지금까지의 최댓값 중 더 큰 값이 기록되게 됩니다.

점화식으로 나타내면 다음과 같습니다.

 

dp[i] = max(p[i] + dp[t[i] + i], max_value);

이후 max_value = dp[i] 로 갱신해 줍니다.

6, 7일차처럼 진행할 수 없는 경우에는 dp[i] = max_value 로 기록해 줍니다.

 

위처럼 뒤에서부터 진행하면, 알고리즘이 자연스럽게 max_value 값을 갱신해 가는 것을 확인할 수 있습니다.

5일차에 dp[5] = p[5] + dp[7]이 되는데, dp[7]은 아직 갱신된 적이 없어 값이 0입니다. 따라서 dp[5] = 15가 됩니다.

다음으로 max_value = dp[5] = 15가 됩니다.

 

4일차에 있는 상담은 하루가 걸리므로, 진행할 수 있습니다.

dp[4] = p[4] + dp[t[4] + 4] = p[4] + dp[5]가 됩니다. p[4] = 20, dp[5] = 15이므로, 합한 값은 35이며, 이는 앞서 기록된 max_value = 15보다 큽니다.

따라서 dp[4] = 35, max_value = dp[4] = 35가 됩니다.

 

3일차에 있는 상담은 하루가 걸리므로, 진행할 수 있습니다.

dp[3] = p[3] + dp[t[3] + 3] = p[3] = dp[4] 가 됩니다. p[3] = 10, dp[4] = 35이므로, 합한 값은 45이며, 이는 앞서 기록된 max_value = 35보다 큽니다.

따라서 dp[3] = 45, max_value = dp[3] = 45가 됩니다.

 

2일차에 있는 상담은 닷새가 걸리므로, 진행할 수 있습니다.

dp[2] = p[2] + dp[t[2] + 2] = p[2] + dp[7] 가 됩니다. p[2] = 20, dp[7] = 0이므로, 합한 값은 20이며, 이는 앞서 기록된 max_value = 45보다 작습니다.

따라서 dp[2] = 45, max_value = dp[2] = 45로 그대로 유지됩니다.

 

1일차에 있는 상담은 사흘이 걸리므로, 진행할 수 있습니다.

dp[1] = p[1] + dp[t[1] + 1] = p[1] + dp[4] 가 됩니다.p[1] = 10, dp[4] = 35이므로, 합한 값은 45이며, 이는 앞서 기록된 max_value = 45와 같습니다.

따라서 dp[1] = 45, max_value = dp[1] = 45로 그대로 유지됩니다.

 

이후 max_value를 출력하면 됩니다.