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

www.acmicpc.net/problem/14501

14501번: 퇴사

[풀이]

DP로 풀 수 있는 문제였다.

DP[i]: i번째 날 상담하면 그 이후부터 최대로 받을 수 있는 이익

상담이 끝나는 날이 N+1보다 커지면 무시한다.

 

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

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

void solution() {
	int ans = 0;
	for (int i = N; i >= 1; i--) {
		//상담이 끝나는 날이 N+1보다 크면
		if (i + T[i] > N + 1)
			continue;
		else {
			int Max = 0;
			for (int j = i + T[i]; j <= N; j++) {
				Max = max(Max, DP[j]);
			}
			DP[i] = P[i] + Max;
			ans = max(ans, DP[i]);
		}
	}
	cout << ans << '\n';
}

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