백준 14501 퇴사

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

- 재귀의 깊이를 보면, 백트래킹으로 풀 수 있는 각이 나온다. 특정 일에 상담을 하는 경우, 하지 않는 경우 2가지의 경우의 수가 있고, N이 15이하이므로 최대 2^15 의 경우의 수가 가능하다. 즉, 시간초과를 걱정 할 필요가 없다.

 

- 첫 호출은 1일차, profit은 0로 한다. 여기서 1일차에 상담을 하기로 결정했다면 1일차의 profit을 현재 profit에 더하고, 상담에 걸리는 시간을 추가해서 호출을 한다.

 

- 백트래킹의 종결조건으로는

 

  1. day가 n+1보다 많은 경우, 즉 퇴사일을 넘기는 경우는 상담을 못 하는 것이기 때문에 return 해 준다.

  2. day가 n+1인 경우는 딱 퇴사일에 도달하는 경우이므로 이 때 maximum값을 갱신한다.

 

- pair vector를 쓰지 않고 날짜, profit 2개의 array를 두어서 코드를 작성하면 더 간단하게 짤 수 있다.

 

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

int n, answer;
using namespace std;

void DFS(int day, int now_profit, vector <pair<int, int>>& v) {
	if (day > n + 1) return;
	if (day == n + 1) {
		answer = max(answer, now_profit);
		return;
	}
	DFS(day + v[day - 1].first, now_profit + v[day - 1].second, v); // 오늘 상담을 하는 경우
	DFS(day + 1, now_profit, v); // 오늘 상담을 하지 않는 경우
}

int main() {
	vector<pair<int, int>> v;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
		v.push_back({ temp1, temp2 });
	}
	DFS(1, 0, v);
	cout << answer << '\n';
	return 0;
}