[삼성SW테스트] 백준 14501번 - 퇴사 (정답률 46%)

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

14501번: 퇴사

삼성SW테스트 기출문제다. 

유형은 dfs 백트래킹 문제로 간단히 풀 수 있다.

 

#include <iostream>
#include <algorithm>
#define INF 987654321
#define maxN 16
using namespace std;
int N;
int T[maxN], P[maxN];
int global_answer = -INF;
 
void dfs(int day, int sum){
    if (day == N+1){
        global_answer = max(global_answer, sum);
        return;
    }
    if (day > N + 1)
        return;
    dfs(day + 1, sum);
    dfs(day + T[day], sum + P[day]);
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N;
    for (int i = 1; i <= N; i++){
        cin >> T[i] >> P[i];
    }
    dfs(1, 0);
    cout << global_answer << '\n';
    return 0;
}