[#14501] 퇴사

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int maxVal = 0;
 
vector<int> time;
vector<int> price;
 
void findAnswer(int start, int currentPrice, const int n) {
    //index가 start부터 시작하고, 현재 가격은 currentPrice
    if (start >= n) {  //끝까지 다 봤으면
        maxVal = max(maxVal, currentPrice);  //최대인지 확인. 최대면 저장
        return;
    }
 
    //경우의 수는 두가지. 상담할 수 있으면 상담 하거나, 상담 안하거나
    if (start + time[start] - 1 <= n - 1) {
        //i번째 상담 할 수 있으면 상담하기
        currentPrice = currentPrice + price[start];
        findAnswer(start + time[start], currentPrice, n);
        currentPrice = currentPrice - price[start];
    }
 
    findAnswer(start + 1, currentPrice, n);  //i번째 상담 안하기
}
 
int main() {
    int n;
    cin >> n;
 
    time = vector<int>(n, 0);
    price = vector<int>(n, 0);
 
    for (int i = 0; i < n; i++) {
        cin >> time[i] >> price[i];
    }
 
    for (int i = 0; i < n; i++)
        findAnswer(i, 0, n);
 
    cout << maxVal;
 
    return 0;
}

 

n의 범위가 작아서 완전 탐색으로 풀었다