[백준 C++] 14501 퇴사 - 브루트포스

14501번: 퇴사

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

vector<pair<int, int>> Schedule;
vector<bool> Solution;
vector<int> Solutions;

void DFS(int N, int Current, int Working, vector<bool> Solution)
{
	if (Working > 0)
	{
		--Working;
	}

	if (Current == N - 1)
	{
		if (Working == 0
			&& Schedule[Current].first <= N - Current)
		{
			Solution[Current] = true;
		}

		int Price = 0;
		int Index = 0;
		for (const bool& Work : Solution)
		{
			if (Work)
			{
				Price += Schedule[Index].second;
			}

			++Index;
		}

		Solutions.emplace_back(Price);

		return;
	}

	Solution[Current] = false;
	DFS(N, Current + 1, Working, Solution);

	if ((Working == 0)
		&& Schedule[Current].first <= N - Current)
	{
		Solution[Current] = true;
		Working = Schedule[Current].first;
		DFS(N, Current + 1, Working, Solution);
	}
}

int main()
{
	int N;
	cin >> N;

	Schedule.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		int T, P;
		cin >> T >> P;
		Schedule.emplace_back(T, P);
	}

	Solution.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		Solution.emplace_back(false);
	}

	DFS(N, 0, 0, Solution);

	cout << *max_element(Solutions.begin(), Solutions.end());
}

---

 

모든 경우를 탐색하는 브루트포스 알고리즘으로 풀었습니다. (DFS, 재귀함수 사용)

 

각 경우의 급여를 저장해서 최대값을 출력하도록 합니다.

경우 설정의 조건은 다음과 같습니다.

 

1. 하루에 한 가지 상담만 진행한다.

2. 상담을 완료하는데 걸리는 기간이 (퇴사날짜 - 현재 날짜)보다 크면 그 상담은 진행할 수 없다.

 

그리고 모든 경우를 탐색하기 위해서는

각 깊이마다 상담을 진행하지 않는 경우를 무조건 탐색해야 합니다.