[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';
}