[백준/C++][퇴사(14501번)]

문제

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

14501번: 퇴사

문제해결

1. 다이나믹 문제이지만 재귀를 이용하여 풀었다.

2. 각 DAY마다 재귀를 이용하여 상담이 가능한 날짜를 탐색했다.

 

코드

#include <iostream>
using namespace std;
int N,Max = 0;
int ary[16][2];
void DFS(int node,int count){
    if(count >= Max){Max = count;}
    for(int i = node;i<=N;i++){
        if(ary[i][0]+i-1>N){continue;}
        DFS(ary[i][0]+i,count+ary[i][1]);
    }
    return;
}
int main(void){
    cin >> N;
    for(int i = 1;i<=N;i++){
        cin >> ary[i][0] >> ary[i][1];
    }
    for(int i = 1;i<=N;i++){
        if(ary[i][0]+i-1>N){continue;}
        DFS(ary[i][0]+i,ary[i][1]);  
    }
    cout << Max;
}