[백준 15486] 퇴사2

https://www.acmicpc.net/problem/15486

남은 N일 동안 최대한 많은 상담을 하려고 한다.

쉽게 생각해보면

day[상담을 잡은 날] = ? //?: ex=3

상담을 잡은 날 + day[상담을 잡은 날] =>ex) 1+array[1] = 1+3 = 4 // 4일째부터 가능

result+=profit[상담을 잡은 날]

일단 가장먼저 생각나는 dfs를 이용한 완전탐색으로 풀어보면

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;



int N;
int day[1500001];
int profit[1500001];
int maxRes = -10000;
void dfs(int 상담날짜,int 총금액) {
	int 금액 = profit[상담날짜];
	총금액 += 금액;
	int 다음상담날짜 = 상담날짜 + day[상담날짜];

	if (다음상담날짜-1 > N)return;
	else maxRes = max(maxRes, 총금액);
	
	
	
	for (int i = 다음상담날짜; i <= N; i++)
	{
		dfs(i, 총금액);
	}

	
}
int main() {
	memset(day, -1, sizeof(int) * 1500001);
	memset(profit, -1, sizeof(int) * 1500001);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		day[i + 1] = a;
		profit[i + 1] = b;

	}

	for (int i = 1; i <= N; i++)
	{
		dfs(i,0);
	}
	cout << maxRes;


}

하지만 이 코드는 시간복잡도가 2^n

결코 n이 150만이므로 구할수가 없다.

따라서 메모제이션을 가미한 DP로 접근을 해봐야한다.

DP과정을 위해서 DP[]라는 배열을 하나 선언한다.

DP배열에 저장되는 값은 "현재 시점에서 벌 수 있는 최대 액수"를 의미한다.

좀 더 구체적으로 말하면 DP[a] = b 의 의미는 "a일때까지의 최대액수는 b원이다"가 된다.

여기서 조심해야할것은 DP[a] 에서 a가 의미하는것은 그날까지가 아닌 그 전날까지를 의미한다.

즉 DP[4] = 10이라고 할때 4일까지 일을 했을 때 벌 수 있는 돈을 의미하는 것이 아니라, 4일전까지 즉 1~3일동안 벌수있는 최대액수를 의미한다.

 

 

dp[1] 은 0

1일날 상담을 받으면 dp[4]를 갱신할수 있다. dp[4] = 10

2일날에는 현재 2일전까지 상담을 해서 벌수있는 금액은 0 dp[2] = 0 dp[7] = 20으로 갱신

3일날에는 dp[3] = 0 dp[4] 를 10으로 갱신할 수가 있는데 dp[4] =10으로 이미 갱신되있으므로 넘어간다.

4일날에는 dp[4] = 10 에다가 dp[5]를 갱신할수 있다 10+20=30 따라서 dp[5] = 30으로 갱신

.단, 일을 함으로써 받게 되는 돈의 날짜가 N + 1 보다 커져버리면 그 일은 할 수 없다.

왜냐하면, N + 1일까지의 값을 계산을 하면 N일까지 일을 했을 때의 최댓값을 구할 수 있지만, 그 이상은 퇴사를 하기 때문에 돈을 못받기 때문이다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;



int N;
int day[1500001];
int profit[1500001];
int dp[1500001];
int maxRes = -10000;


int main() {
	memset(day, -1, sizeof(int) * 1500001);
	memset(profit, -1, sizeof(int) * 1500001);
	memset(dp, 0, sizeof(int) * 1500001);
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		day[i + 1] = a;
		profit[i + 1] = b;

	}

	

	for (int i = 1; i <= N+1 ; i++)
	{
		maxRes = max(maxRes, dp[i]);
		
		if (i + day[i] > N + 1)continue;
		
		dp[i + day[i]] = max(maxRes + profit[i], dp[i + day[i]]);
		 
	}
	cout << maxRes;



}