[백준] 14501번 퇴사

14501번: 퇴사

완전 탐색, DP 두 가지 방법으로 풀 수 있다.

완전 탐색은 1일부터 차근차근 가능한 날을 모두 골라 최댓값을 구해주면 되고

 

DP는

i 일에 얻는 이익 = max(i 일을 선택할 때 얻는 최대 이익, i 일을 선택하지 않을 때 얻는 최대 이익)

→ i 일에 얻는 이익 = max(i 일을 선택할 때 얻는 이익 + i+T[i]일에 얻는 최대 이익, i+1일에 얻는 최대 이익)

→ DP[i] = max(P[i] + DP[i + T[i]], DP[i + 1])

라는 점화식을 세워주고 재귀로 구현하면 된다.

 

1. 완전 탐색

#include <iostream>
#include <algorithm>
using namespace std;
int N, Max;
int T[16], P[16];
void BruteForce(int idx, int res) {
	if (idx > N) Max = max(Max, res);
	else {
		for (int i = idx; i <= N; i++) {
			if (i + T[i] > N + 1) BruteForce(i + T[i], res);
			else BruteForce(i + T[i], res + P[i]);
		}
	}
}
int main() {
	cin >> N;
	for (int n = 1; n <= N; n++) cin >> T[n] >> P[n];
	BruteForce(1, 0);
	cout << Max;
	return 0;
}

 

2. DP

#include <iostream>
#include <algorithm>
using namespace std;
int N;
int T[16], P[16];
int DP(int idx) {
	if (idx > N) return 0;
	if (idx + T[idx] > N + 1) return max(DP(idx + T[idx]), DP(idx + 1));
	else return max(P[idx] + DP(idx + T[idx]), DP(idx + 1));
}
int main() {
	cin >> N;
	for (int n = 1; n <= N; n++) cin >> T[n] >> P[n];
	cout << DP(1);
	return 0;
}