백준 14501번 - 퇴사1
Updated:
C++
14501번 - 퇴사
문제
상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
접근 방법 및 구현
동적 계획법으로 풀어야 하는 문제이다.
동적 계획법 문제는 정말 다양한 점화식으로 접근 할 수 있는데, 제가 푼 방법을 소개해 드리겠습니다.
이 코드는 세 부분으로 나누어 지는데,
- 현재 상담의 금액 + 현재 상담일에서 벌어 놓은 돈 : P[i] + dp[i]
- 현재 상담 만큼의 기간 T[i]이 걸린 이후에 벌어 놓은 돈 : dp[i + T[i]]
- 현재 벌어 놓은 돈과 전날 벌어 놓은 돈을 비교 : max(dp[i], dp[i-1])
말로는 설명하기 어려우니, 표를 통해서 설명해드리겠습니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| T | 5 | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | x |
| P | 50 | 40 | 30 | 20 | 10 | 10 | 20 | 30 | 40 | 50 | x |
| DP | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
해당 문제의 마지막 테스트 케이스를 사용했습니다.
기존 DP값은 모두 0이며 첫번째 상담 부터 탐색합니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| T | 5 | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | x |
| P | 50 | 40 | 30 | 20 | 10 | 10 | 20 | 30 | 40 | 50 | x |
| DP | 0 | 0 | 0 | 0 | 0 | 50 | 0 | 0 | 0 | 0 | 0 |
첫번째 상담이 끝난 이후입니다.
첫번째 상담 일이 끝나는 날은 i + T[i] == 6 입니다.
dp[i + T[i]] 는 당연히 0이며, P[i] + dp[i]는 50이므로 0 < 50 으로 dp[6]에 50이 저장 됩니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| T | 5 | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | x |
| P | 50 | 40 | 30 | 20 | 10 | 10 | 20 | 30 | 40 | 50 | x |
| DP | 0 | 0 | 0 | 0 | 0 | 50 | 0 | 0 | 0 | 0 | 0 |
두번째 상담이 끝난 이후입니다. 앞선 결과와 달라지지 않았는데! 이유는,
두번째 상담이 끝난 날 i + T[i] == 2 + 4 == 6 이며, P[i] + dp[i] == 40 + 0 == 40
이는 첫날에 dp에 넣은 상담이 끝났을 때의 결과 50보다 작은 값이라 변하지 않았습니다.
이러한 이유로 2,3,4,5일은 전부 첫 날에 상담결과에 밀려 변동이 없습니다.
6, 7일째 상담을 진행하면
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| T | 5 | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | x |
| P | 50 | 40 | 30 | 20 | 10 | 10 | 20 | 30 | 40 | 50 | x |
| DP | 0 | 0 | 0 | 0 | 0 | 50 | 60 | 0 | 80 | 0 | 0 |
입니다. 알아서 상담을 할 시에 제일 큰 돈을 벌 수있는 방법을 추려내고 있습니다.
하지만 문제는! 8일 째 입니다.
만약 이대로 8일째에 비교를 한다면 dp[8 + 3] = P[8] + dp[8] == 30 + 0으로 30이 됩니다.
하지만 알다시피, 이전에 60만큼의 돈을 벌어 놓았으므로, 60 + 30으로 90이 되어야합니다.
따라서 여기서 필요한 코드가
dp[i] = max(dp[i], dp[i - 1]);
입니다.
이를 통해 이때까지 벌어놓은 돈 중 가장 많이 번 돈을 해당 dp에 옮겨주어, 60만큼을 벌어놨다라고 구현해줍니다.
이를 통해, 8일째 상담을 끝내면,
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| T | 5 | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | x |
| P | 50 | 40 | 30 | 20 | 10 | 10 | 20 | 30 | 40 | 50 | x |
| DP | 0 | 0 | 0 | 0 | 0 | 50 | 60 | 60 | 80 | 0 | 90 |
으로 가장 많이 번 돈은 90이 됩니다!
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define maxN 17
int n;
int dp[maxN];
int T[maxN]; //상담을 완료하는데 걸리는 기간
int P[maxN]; //해당 상담을 끝냈을 때, 받을 수 있는 금액
int main(int argc, char* argv[]) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> T[i] >> P[i];
}
//첫번째 상담 부터 시작한다.
for (int i = 1; i <= n; i++) {
//만약 그 날 상담이 되어 있지 않을 때를 대비하여, 전날에 결과 dp를 당일에 복사한다.
dp[i] = max(dp[i], dp[i - 1]);
//현재 상담을 완료한 시점 < dp값이 현재 상담 금액 + 현재까지 번 돈 일시
if (dp[i + T[i]] < P[i] + dp[i]) {
dp[i + T[i]] = P[i] + dp[i];
}
}
//가장 많이 돈을 번 상담 금액을 출력
cout << *max_element(dp + 2, dp + n + 2);
return 0;
}
후기 및 개선할 점
후기:
DP 문제는 고민하는 시간 대비, 코드는 정말 짧다. 이 문제도 정말 오래 고민하고, 다른 블로그를 참고하여 제대로 풀 수 있었다. DP가 제일 힘들어..
