#14501번 퇴사 (C++)

링크 : www.acmicpc.net/problem/14501

14501번: 퇴사

문제 풀이는 다음과 같다.

1. N+1일이 퇴사일이라는 점을 기억하자.

2. 백트래킹 - DFS를 통해 모든 경로를 구한다. 경로를 구하는 방법은 다음과 같다.

(1) 현재 날짜에서 업무 날짜를 더한 값이 퇴사일을 초과하지 않으면 돈을 누적하여 dfs를 진행한다.

(2) 현재 날짜의 다음날이 퇴사일을 초과하지 않으면, 해당일부터 또다시 새로운 dfs를 진행한다. 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, res, a, b = 0;
vector<pair<int, int>> v;
vector<int> ans(16, 0);

void dfs(int day, int money) {
	res = max(money, res);
	if (day >= n + 1) return;
	if (day + v[day].first <= n + 1) dfs(day + v[day].first, money + v[day].second);
	if (day + 1 <= n + 1) dfs(day + 1, money);
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	v.push_back(make_pair(0, 0)); // 1번째부터 시작하기 위함
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a >> b;
		v.push_back(make_pair(a, b));
	}
	dfs(1, 0);
	cout << res << "\n";

	return 0;
}

참고로 이 문제는 DP(동적 프로그래밍)로도 풀수 있다. 

DP는 여전히 한번에 해결책이 떠오르지 않는다.