백준 14501 퇴사

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

 

서론

DP문제. 재귀를 이용해서 풀이.

 

---

풀이

완전탐색이랑 유사하게 구현했는데 다만 모든 경우의 수를 탐색하지는 않고 최대값이 나올만한 경우의 수만 탐색한다.

예제에서 1일에 일한 후 면 4일과 5일에도 일을 하지 1일만 일하고 끝내는 경우는 나오지 않는다. 즉 일할 수 있는 최대한으로 일한다.

void dfs(int idx, int sum) { // idx = 날짜
	if (idx > n) {
		result = max(result, sum);
		return;
	}
    
    // 현재 날짜에선 일을 하지 않음, sum을 그대로 넘겨줌
	dfs(idx + 1, sum);
    // 현재 날짜에서 일을 함, 다음 idx는 T만큼 이동해야함, sum에 P를 더해줌
	if (idx + table[0][idx] <= n + 1) dfs(idx + table[0][idx], sum + table[1][idx]); 
	return;

}

 

---

구현

// c++

#include <algorithm>
#include <iostream>

using namespace std;

int table[2][16];
int n;
int result;

void init() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> table[0][i] >> table[1][i];
	}
}

void dfs(int idx, int sum) {
	//cout << idx << endl;
	if (idx > n) {
		result = max(result, sum);
		//cout << sum << endl;
		return;
	}
	dfs(idx + 1, sum);
	if (idx + table[0][idx] <= n + 1) dfs(idx + table[0][idx], sum + table[1][idx]);
	
	return;

}

int main() {
	init();
	dfs(1, 0);
	cout << result;
}