[BOJ] 퇴사(14501)

[백준(BOJ)] 퇴사(14501) C++

문제 : BOJ_14501번 퇴사

문제 설명

완전 탐색

n 개의 날이 있고, n+1일째 퇴사를 합니다.

이때 각 요일마다 할 수 있는 일에 필요한 기간과 그에 대한 보상이 각각 주어집니다.

n+1 째는 퇴사하므로 일할 수 없고, n 일 안에 처리할 수 있는 일들 중에서 최대한의 보상을 받을 수 있게 할 일을 골라야 합니다.

n이 최대 15임으로 완전 탐색으로 해결할 수 있습니다.(O(2^n))

---

Solution

재귀 함수를 만들고, 해당 일을 선택하는 경우와 선택하지 않는 경우로 마지막 일까지 순회합니다.

이때, expired를 만들어서 이전 요일에서 선택한 일에 대한 일을 하는 중이 아닌 경우 현재 일을 선택하는 경우로 재귀 함수를 사용할 수 있습니다.

---

Description

• n 일 재까지 재귀가 돌고, 다음 n+1로 재귀 함수가 돌기 때문에, 보상의 총합을 확인하는 경우는 n+1인 경우로 했습니다.

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int result, n;
vector<pair<int,int>> adj;
void recursion(int idx, int expired, int total){
    if(idx==n+1){
        result = max(result, total);
        return;
    }
    recursion(idx+1,expired,total);
    if(idx+adj[idx].first-1<=n && expired<idx){
        recursion(idx+1,idx+adj[idx].first-1,total+adj[idx].second);
    }
}
int main(){
    cin >> n;
    adj.resize(n+1);
    for(int i=1;i<=n;i++){
        int day, value;
        cin >> day >> value;
        adj[i]={day,value};
    }
    for(int i=1;i<=n;i++){
        recursion(1,0,0);
    }
    cout << result << '\n';
}