[백준/BOJ] 백준 14501번 : 퇴사

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

14501번: 퇴사

완전 탐색(브루트 포스)을 이용해 문제를 풀었다.

가능한 상담을 모두 탐색해, 최대 이익을 얻었다.

어떠한 상담을 하는데 그 일이 퇴사일 이상 끝날 때의 상담은 추가하지 않았지만, 정확히 퇴사일 전날 끝나는 상담이라면 추가하였다. 이러한 판단은 어떠한 상담을 하고 난 다음, 상담 가능한 최소 날짜를 만들어 구분하였는데, 만약 상담 A를 하고 난 뒤, 다음에 상담할 수 있는 최소 날짜가 정확히 퇴사일이라면, 상담 A를 끝나면 퇴사일 전날이라 가능하고, 최소 날짜가 그 이후라면 상담 A는 불가능하다.

 

코드 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> t;
vector<int> p;

int solve(vector<int> inputday, int nextminday)
{
	int ret = 0;

	//다음 할 수 있는 최소 날이 범위를 넘어갈때
	if (nextminday > n-1)
	{
		for (int i = 0; i < inputday.size()-1; i++)
		{
			ret += p[inputday[i]];
		}
		//정확히 퇴사하기 전날 끝나는 경우의 것은 추가
		if (nextminday == n)
			ret += p[inputday.back()];

		return ret;
	}

	for (int i = 0; i < n; i++)
	{
		if (i >= nextminday)
		{
			inputday.push_back(i);
			ret = max(ret, solve(inputday, i+t[i]));
			inputday.pop_back();
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int temp1, temp2;
	int maxmoney;
	vector<int> tempvector;

	cin >> n;
	//0~n-1일로 구분한다.
	for (int i = 0; i < n; i++)
	{
		cin >> temp1;
		cin >> temp2;
		t.push_back(temp1);
		p.push_back(temp2);
	}
	maxmoney = solve(tempvector, -1);

	cout << maxmoney;

	return 0;
}