[BOJ] 백준 14501 퇴사

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

지금 종만북에서 6장 무식하게 풀기를 공부하고 있는중에 발견한 문제.
딱 보니 브루트포스 문제 같아서 처음으로 문제풀이를 했다.

퇴사하기 전 돈을 많이 벌고싶은 마음에 남은기간동안 최대로 돈을 버는 법을 연구하는 문제.

이 날짜가 최선으로 믿고 일단 간다음, 일정한 기간 내에 해결이 되지 않는다면
다시 되돌아오는 문제이다. 따라서 재귀함수를 이용한 브루트포스이다.

소스코드 :

#include
#include 
using namespace std;

int maxNum = 0;

int Max(int a, int b) {
	if (a >= b) return a;
	else return b;
}

int BruteForce(vector < pair > & v, int payment, int s) {
	// Base Case, 일정이 1개인경우와 일정을 초과해버리는 경우이다.
	if (v.size() == 1)
		return v[0].first == 1 ? v[0].second : 0;
	if (s > v.size()) {
		return 0;
	}
	if (maxNum < payment) maxNum = payment;

	int tmp = 0;
	for (int i = s; i < v.size(); i++) {
		payment += v[i].second;
		tmp = BruteForce(v, payment, i + v[i].first);
		payment -= v[i].second;
	}
	return Max(payment, tmp);


}


int main() {
	int N;
	cin >> N;
	vector > v;
	for (int i = 0; i < N; i++) {
		int T, P;
		cin >> T >> P;
		v.push_back({ T,P });
	}
	
	int tmp=  BruteForce(v, 0, 0);
	cout << Max(tmp, maxNum) << endl;
}