백준 : 14501 - 퇴사

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

 

음.. 그냥 가능한 경우의 수를 전부 탐색하면 되는 문제였다

완전탐색에 dfs 비슷한 느낌..??

 

이렇게 모든 날짜의 상담을 [days, pay] 형태로 제공해 주니까

그냥 배열의 index를 날짜로 생각하고 저장해두면 되었다.

 

그 다음부터는 dfs랑 똑같은데, 1일 상담을 하는상황.. -> 4 ~ 7 일 중 하나를 선택해서 상담 ..... 이렇게 가지치기를 반복해주면 된다.

 

처음에는 1일 상담을 받으면 -> 무조건 4일상담을 받도록 구현했는데

(마지막 테스트케이스에도 있지만) 중간에 상담없는 날이 껴있을 때 전체 pay가 많아지는 상황이 생긴다.

그래서 오늘로부터, 선택할 수 있는 모든 상담에 대해 test를 해봐야 한다.

 

---

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

int n;
vector<pair<int, int>> sangdams; // [days, pay]

int maxmoney = 0;

void sol(int index, int money){
    if(index >= n){
        // 불가능한 상담
        maxmoney = max(maxmoney, money);
        return;
    }
    int next = index + sangdams[index].first;
    if(next > n){
        // 불가능한 상담, 이 상담은 안하고 끝내야함
        maxmoney = max(maxmoney, money);
        return;
    }else if(next == n){
        // 지금게 마지막 상담
        money+=sangdams[index].second;
        maxmoney = max(maxmoney, money);
        return;
    }
    money+=sangdams[index].second;

    for(int i = 0; i<n; i++){
        sol(next+i, money);
    }
    
}

int main(){

    cin >> n;

    for(int i = 0; i<n; i++){
        int a, b;
        cin >>a >> b;
        sangdams.push_back({a, b});
    }

    for(int i = 0; i<n; i++){
        sol(i, 0);
    }

    cout << maxmoney;

    return 0;
}