(c++)백준 15486번: 퇴사 2

www.acmicpc.net/problem/15486

15486번: 퇴사 2

[풀이]

2020/09/14 - [백준/DP] - (c++)백준 14501번: 퇴사

(c++)백준 14501번: 퇴사

이전에 퇴사 문제를 푼 방식대로 N번째 날부터 거꾸로 DP를 사용하여 풀려고 했지만 N의 크기가 커졌기 때문에 시간초과가 났다.

그래서 앞에서부터 현재까지 벌 수 있는 최대 이익을 계산하는 방식으로 DP를 사용했다.

DP[i]: i번째 전날까지 상담해서 벌 수 있는 최대 이익

점화식

Max: 지금까지의 벌 수 있는 최대 이익

DP[i + T[i]] = max(DP[i + T[i]], Max + P[i]);

 

#include <iostream>
#include <algorithm>//max
#define Max 1500001
using namespace std;

int N;
int T[Max];
int P[Max];
int DP[Max] = { 0, };

void solution() {
	DP[1] = 0;
	int ans = 0;
	for (int i = 1; i <= N + 1; i++) {
		ans = max(ans, DP[i]);
		if (i + T[i] > N + 1)
			continue;
		else {
			DP[i + T[i]] = max(DP[i + T[i]], ans + P[i]);
		}
	}
	
	cout << ans << '\n';
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> T[i] >> P[i];
	}
	solution();
	return 0;
}