문제 정보
백준 ( BOJ ) 14501 퇴사
문제 풀이 : DP
문제 출처 : https://www.acmicpc.net/problem/14501
문제 원 출처 : 삼성 역량테스트 코딩테스트 기출 문제
문제 풀이
가장 대표적인 DP 방식의 문제 풀이 입니다.
현재 날짜의 상담을 받았을 경우 그 상담이 끝난 후 날짜의 기초값에 현재날짜 금액을 더해가며
풀어 나가면 됩니다.
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200
이 예시를 통해서 같이 설명을 드릴께요
1일차 :
3일 뒤 10을 더함
0 0 0 10 0 0 0 0 0
2일차 :
5일뒤 20을 더함
0 0 0 10 0 0 20 0 0
3일차 : 1일뒤 10을 더함 0 0 0 20 0 0 20 0 0
4일차 : 1일뒤 20을 더함 0 0 0 20 40 0 20 0 0
5일차 : 2일뒤 15를 더함 0 0 0 20 40 0 55 0 0
6일차 : 넘어감으로 스킵
7일차 : 넘어감으로 스킵
결과적으로 55가 최대가 되겠죠.
하지만 여기서 간과하면 안되는 문제가 있습니다.
바로 x일째를 스킵 할때 문제가 생깁니다.
10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50
이 예제를 통해서 보시면 중간에 빠지는 부분이 생기게 됩니다.
그래서 어떻게 해결하느냐 하면,
x일째의 계산을 마친 후 그 영역부터 끝까지 모두 같은 값으로 만들어 주는 겁니다.
물론 더 큰 dp는 그대로 두고, 더 작은부분만 더해주면 됩니다.
문제 코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
int tempDay, tempCost;
int temp;
cin >> n;
vector<int> cost(n + 1, 0);
vector<int> day(n + 1, 0);
vector<int> dp(n + 1, 0);
for (int i = 0; i < n; i++) {
cin >> tempDay >> tempCost;
cost[i] = tempCost;
day[i] = tempDay;
}
for (int i = 0; i < n; i++) {
if (i + day[i] > n)
continue;
if (dp[i + day[i]] < dp[i] + cost[i]) {
dp[i + day[i]] = dp[i] + cost[i];
for (int j = i + day[i]; j <= n; j++) {
if (dp[j] < dp[i + day[i]]) {
dp[j] = dp[i + day[i]];
}
}
}
}
cout << dp[n];
return 0;
}