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

14501번: 퇴사

cpp

#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. 상담을 완료하는데 걸리는 기간이 (퇴사날짜 - 현재 날짜)보다 크면 그 상담은 진행할 수 없다.

 

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

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