[C++]BOJ 14501 - 퇴사

n이 최대 15이기 때문에 최악의 경우에도 2^15가지의 경우의 수를 가진다.
따라서 완전탐색을 해도 문제가 없다.
하지만 동적 계획법으로도 해결할 수 있기 때문에 두가지 방법을 다뤄보겠다.

먼저 깊이우선탐색을 이용한 방법이다. (이전 금액을 가져와 최종적으로 비교해야 하기 때문에 dfs를 사용한다.)
현재 day에서 선택 할지 안 할지를 재귀적으로 호출한다.
결과적으로 최종 money를 비교해 ans에 저장한다.

#include <iostream>
using namespace std;
int n, ans, t[16], p[16];
void dfs(int day, int money) {
	if(day > n + 1) return;
	if(day == n + 1) {
		if(ans < money) ans = money;
		return;
	}
	dfs(day + t[day], money + p[day]);
	dfs(day + 1, money);
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> t[i] >> p[i];
	dfs(1, 0);
	cout << ans;
}

동적 계획법을 이용한 방법이다.
dp[i + t]값 보다 dp[i] + p값이 크다면 dp[i + t]에 dp[i] + p를 넣는다.
내일까지 벌 수 있는 최대 금액보다 오늘 벌 수 있는 최대 금액이 더 크다면 내일도 오늘만큼 벌 수 있으므로 dp[i + 1] = dp[i] 한다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, t, p, dp[16];
int main() {
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> t >> p;
		dp[i + t] = max(dp[i + t], dp[i] + p);
		dp[i + 1] = max(dp[i + 1], dp[i]);
	}
	cout << dp[n];
}