[c++] 백준-퇴사2 (dynamic programming)

1. 문제

 

2. 입출력

 

---

3. 문제 해설

 

이 문제는 그냥 퇴사와 퇴사2가 존재한다. 두 문제는 완전 같은데 다른 점이 하나 있다.

바로 N의 범위가 1000에서 1500000으로 늘어났다는 점이다. 이는 완전탐색으로 O(N^2) 시간 복잡도가 가능했었는데 N이 증가함에 따라 완전탐색 알고리즘은 사용하지 못한다는 뜻이다. 

 

N의 범위가 1500000으로 늘어났으니 가능한 알고리즘 시간 복잡도는 O(N) or O(NlogN)정도가 되겠다. 

그러면 가자 대표적인 것이 dp-> dynamic programming을 이용해보기로 했다. 

 

위와 같이 dp를 사용해보기로 한 것은 이전 값의 입력들이 그 다음 입력에 영향을 미치는 관계가 있다고 생각이 들었기 때문이다. 

1일차의 상담을 선택하거나 선택하지 않을 수 있는데 이와 같은 식을 점화식으로 나타내면 O(N)안에 문제를 해결할 수 있을 거 같았다. 

 

상담을 하고 돈을 받는 날은 1일에 3일이 걸리는 상담을 했다면 4일에 돈을 받는 것을 확정할 수 있다. 따라서 돈을 받는 날은 

i + days[i]에 해당한다.

 

또한 dp문제는 다음 3가지 프로세스가 중요하다. 

• dp배열의 차원과 dp배열이 의미하는 바
• dp 점화식
• 초기 값 설정

나는 dp 배열을 1차원으로 설정했고 dp[i]는 i번째 날에 얻을 수 있는 최대 이익으로 설정했다. 

그리고 dp점화식으로는 max(dp[i], dp[i-1])로 이전의 날이 더 크다면 오늘 얻을 수 잇는 이득은 dp[i-1]이 dp[i]가 되므로 이 과정을 수행해준 후 

dp[i+days[i]] = max(dp[i+days[i]] , dp[i] + value[i]);

위와 같이 점화식을 세워주었다. 

dp[i]가 차례대로 계산되는 것이 아니라 앞선 입력부터 끝나는 날에다가 차례 차례 값을 갱신해주었기 때문에 이미 dp[i]에는 이전 차례까지의 얻을 수 있는 최대 이익이 들어있을 것이고 현재 i에 해당하는 것을 선택하는 지와 선택하지 않는 지만 판별해주기 때문이다. 

위의 예시를 생각해보자 

	1	2	3	4	5	6	7	8
days[i]	3	5	1	1	2	4	2
value[i]	10	20	10	20	15	40	200

• dp[1] - dp[1]에서 얻을 수 있는 돈은 없다. 0 , dp[1+3] = max(dp[3+1] , dp[1] + value[1]) = max(0,10) = 10
• dp[2] - dp[2]에서 얻을 수 있는 돈은 없다. 0 , dp[2+5] = max(dp[2+5] , dp[2] + value[2]) = max(0,20) = 20
• dp[3] - dp[3]에서 얻을 수 있는 돈은 없다. 0, dp[3+1] = max(dp[3+1] , dp[3] + value[3]) = max(10,10) = 10
• dp[4] - dp[4]에서 얻을 수 있는 돈은 앞서 계산한 10 dp[4+1] = max(dp[4+1] , dp[4]+value[4]) = max(0,30)=30
• dp[5] - dp[5]에서 얻을 수 있는 돈은 앞서 계산한 30 dp[5+2] = max(dp[5+2] , dp[5]+value[5])=max(20, 30+15)=45
• dp[6] - dp[6]에서 얻을 수 있는 돈은 앞서 계산한 값 중 가장 큰 45 dp[6+4]는 범위를 넘어가니 계산안해도 된다.
• dp[7] - dp[7]에서 얻을 수 있는 돈은 앞서 계산한 값 중 가장 큰 45 dp[7+2]도 범위를 넘어가니 계산 안해도 된다.

위와 같은 과정으로 dp배열을 찾아가면 정답을 찾을 수 있다. 

 

---

4. 코드

#pragma warning (disable : 4996)
/*
	N이 1500000 의 범위를 가지므로 O(N^2)으로는 풀지 못한다. 
	O(N)이나 O(NlogN)으로 풀어야한다. 
*/
#include <cstdio>
#include <algorithm>
#define MAX 1500000+4
using namespace std;
int N;
int value[MAX];
int days[MAX];
int dp[MAX + 1000];
int ans;
int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &days[i], &value[i]);
		dp[i] = max(dp[i], dp[i - 1]);
		dp[i + days[i]] = max(dp[i + days[i]], dp[i] + value[i]);
		ans = max(ans, dp[i + days[i]]);
	}	

	/*for (int i = 0; i <= N + 1; i++) {
		printf("%d ", dp[i]);
	}*/
	printf("%d\n", dp[N] < dp[N + 1] ? dp[N + 1] : dp[N]);
	return 0;
}