백준 15486 퇴사 2 C++

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

15486번: 퇴사 2

전형적인 dp 문제입니다.

 

주어진 입력에 대해 i + T 일에 돈이 들어온다고 생각하면 dp[i+T] = max(dp[i + T], current + P) 입니다.

 

왜냐하면 1번째 날부터 이어온다고 생각하면 현재 벌 수 있는 최대값 current와 i번째 날부터 일을 시작했을 때 버는 돈 P원의 합은 i+T일의 최대 수입은 current+P 또는 dp[i+T] 입니다. 이 때 n+1 일을 넘는 부분에 대해서는 계산을 하면 안 됩니다.

 

코드는 다음과 같습니다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, t, p;
int arr[1500002][2];
int dp[1500002];

void init()
{
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> t >> p;
		arr[i][0] = t;
		arr[i][1] = p;
	}
	memset(dp, 0, sizeof(dp));
}

// i 번 째 날 t 일 일 한 거 : i+t 일에 돈 들어온다고 생각
// dp[x] = max(dp[x], P_i + current) (i+t=x, current : 현재 최대 수입)
// n+1보다 큰 날은 계산 금지

int getResult() {
	int result = 0;
	int current = 0; // 현재 날 까지 최대값

	for (int i = 1; i <= (n + 1); i++) {
		int T = arr[i][0];
		int P = arr[i][1];

		int x = i + T;
		current = max(current, dp[i]);
		if (x > (n + 1)) {
			result = max(result, current);
		}
		else {
			dp[x] = max(dp[x], P + current);
			result = max(result, current);
		}
	}

	return result;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
	cout << getResult();
}