[백준, 14501번] 퇴사 (다이나믹 프로그래밍 : DP, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 퇴사" 문제는 퇴사 전 최대 수익을 창출할 수 있는 상담을 선택하여 최대 수익을 내는 것 입니다.

 

• 상담 기간과 수익이 주어지며, 특정 상담을 수행하면 해당 상담 기간만큼의 날이 소요됩니다.
• 퇴사일 이후로 상담이 넘어가면 해당 상담은 수행할 수 없습니다.
• 최대 수익을 구하기 위해 DP를 활용합니다.

 

문제 자체는 어렵지 않으나 점화식을 도출하는 과정이 까다롭습니다. 우리의 목표는 퇴사 전 최대 수익을 뽑는 것인데, 각 날짜에서 상담을 선택하거나 선택하지 않는 경우를 고려하고, 이전까지의 최적해를 활용하여 현재의 최적해를 구하는 동적 계획법의 특성을 잘 활용해야 합니다.

 

특히 상담이 걸리는 기간과 수익을 고려하면서 dp 배열에 각 날짜까지의 최대 수익을 저장하고, 이를 활용하여 최종적으로 퇴사일까지의 최대 수익을 구할 수 있습니다.

---

말 보다 그림으로 보는 것이 편하기 때문에..

 

위와 같이 각 날짜에서 최대 수익을 저장하는 DP 배열을 사용하여 예제 1번의 정답을 도출하는 과정을 살펴보겠습니다.

 

그 전에 정리하자면:

• i : 현재 날짜
• T[i] : i일에 시작하는 상담이 걸리는 기간
• i + T[i] : i일에 시작한 상담이 끝나고 난 다음 날
• P[i] : i일에 시작하는 상담의 수익
• dp[i] : i일까지 얻을 수 있는 최대 수익

---

 

1 일차 : 오늘(i일) 상담을 했을 때 상담이 끝나는 날의 최대 수익은, 그 날짜에 이미 계산된 수익과 (오늘까지의 최대 수익 + 오늘 상담 수익) 중 더 큰 값을 선택합니다.

 

2 일차 : 마찬가지로 오늘(2일) 상담을 했을 때 상담이 끝나는 날(7)의 최대 수익은, 7일차의 이미 계산된 수익과 (2일차까지의 최대 수익 + 오늘 상담 수익 : 20) 중 더 큰 값을 선택합니다.

 

 

3 일차 : 마찬가지로 오늘(3일) 상담을 했을 때 상담이 끝나는 날(4)의 최대 수익은, 4일차의 이미 계산된 수익과 (3일차까지의 최대 수익 + 오늘 상담 수익 : 10) 중 더 큰 값을 선택합니다.

 

4 일차 : 오늘(4일) 상담을 했을 때 상담이 끝나는 날(5)의 최대 수익은, 5일차의 이미 계산된 수익과 (4일차까지의 최대 수익 + 오늘 상담 수익 : 20) 중 더 큰 값을 선택합니다.

 

5 일차 : 오늘(5일) 상담을 했을 때 상담이 끝나는 날(7일)의 최대 수익을 계산합니다.

 

7일차에는 이미 2일차 상담으로 인한 수익 20만원이 저장되어 있습니다. 이것과 (5일차까지의 최대 수익 30만원 + 5일차 상담 수익 15만원 = 45만원)을 비교합니다. 45만원이 기존 값인 20만원보다 크므로 dp[7]은 45만원으로 업데이트됩니다.

 

6일차 : 6일차에 상담을 시작하면 상담이 끝나는 날은 10일(6 + 4)입니다. 따라서 이 상담은 퇴사일(8일)을 초과하기 때문에 선택할 수 없습니다. dp[10] = max(30 + 40, 45)와 같은 계산은 의미가 없습니다

 

---

즉, 문제의 핵심은 퇴사 전까지 최대의 수익을 내야하는 것이기 때문에, 오늘 상담했을 때 퇴사일을 넘어가지 않는 선에서 최대한 효율적인 상담을 해야합니다.

 

따라서 1일차부터, 상담이 끝났을 때 다음날의 최대 수익을 저장하고, 각 날짜에서 이미 계산된 최대 수익과 새로운 상담을 했을 때의 수익을 비교하면서 최적의 해를 찾아갑니다.

 

왜냐하면 같은 날짜에 도달할 수 있는 여러 가지 경우가 존재하기 때문입니다. 예를 들어 7일차에는:

1. 2일차에 시작한 상담(5일 소요)으로 20만원을 벌 수 있고
2. 5일차에 시작한 상담(2일 소요)과 이전 수익을 합쳐 45만원을 벌 수 있습니다.

이처럼 같은 날짜에 도달하더라도 어떤 상담들을 선택했는지에 따라 수익이 달라질 수 있으므로, 매번 최대값을 비교하고 저장하면서 최적의 해를 찾아가는 것입니다.

 

전체 코드

 

상담이 불가능한 경우(퇴사일을 초과한다면) 현재값(dp[i+1])과 이전까지의 최대 수익(dp[i]) 중 더 큰 값을 선택하여 최소한 이전까지의 최대 수익은 보장받을 수 있도록 합니다.