[BOJ] #14501 _ 퇴사

[퇴사] https://www.acmicpc.net/problem/14501

14501번: 퇴사

dfs를 이용하여 모든 경우의 수를 해보고, 최대 수익을 구하였다.

찾아보니 DP를 이용해 풀 수도 있다.

 

[ 소스 코드 ]

 

#include <cstdio>
#include <algorithm>
#define MAX 15

using namespace std;

int N, T[MAX + 1], P[MAX + 1];
int result = 0;

void solve(int day, int TotalPrice);
int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &T[i], &P[i]);
	}

	solve(1, 0);

	printf("%d\n", result);

	return 0;
}

void solve(int day, int TotalPrice) {
	if (day > N) {
		result = max(result, TotalPrice);
		return;
	}

	if (day + T[day] <= N + 1) solve(day + T[day], TotalPrice + P[day]);
	if (day + 1 <= N + 1) solve(day + 1, TotalPrice);

}