[백준 14501번 - 퇴사] C++ 풀이

백준 14501번.

 

사용한 알고리즘

- dfs

 

N이 최대 15이기 때문에, dfs 재귀로 시도를 먼저 해보았다. 

i번째 날부터 시작한다고 가정했을 때 dfs 를 호출한다. (총 N번 호출)

각 경우마다, 해당 날에 상담을 하고, 다음 상담 가능일부터~ N일 까지 dfs 를 호출한다. (N - 현재 날 - Ti 번 호출)

현재 날짜에 해당 상담을 하면 N일이 넘어가거나, N일이면 반환.

 

완성 코드

#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;
int n;
vector<pair<int, int>> v;
int ans = 0;

void dfs(int time, int curr_t, int result) {
	if (time + curr_t > n) {
		ans = (result > ans) ? result : ans;
		return;
	} else if (time + curr_t == n) {
		ans = (result + v[time].second > ans) ? result + v[time].second : ans;
		return;
	} else {
		for(int i = 0; i < n - time - curr_t; ++i) {
			dfs(time + curr_t + i, v[time + curr_t + i].first, result + v[time].second);
		}
	}
}

int main() {
	scanf("%d", &n);

	for(int i = 0; i < n; ++i) {
		int t, p;
		scanf("%d %d", &t, &p);
		v.push_back(make_pair(t, p));
	}
	for(int i = 0; i < n; ++i) {
		dfs(i, v[i].first, 0);
	}
	printf("%d\n", ans);
}

 

풀고 나서 다른 분들의 풀이를 살펴보니 dp 로 푸는 것이 더 간단할 것 같다.

 

dp[오늘] = max(dp[오늘 스케줄 소화할 경우], dp[오늘 스케줄 소화하지 않을 경우])