[BOJ] - 14501. 퇴사

[URL]

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

14501번: 퇴사

[풀이 과정]

1. 조건에 맞게 기본 DFS 시전

2. sum += PAY[pos];

3. pos: 1~ N까지 다 검사 후 sum 중 최대값 출력

 

[소스 코드]

// 4. 퇴사
// https://www.acmicpc.net/problem/14501
 
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int N;
int Time[16];
int Pay[16];
 
int cand[987654];
int cnt = 0;
int Max = 0;
 
void input() {
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d %d", &Time[i], &Pay[i]);
    }
}
 
void dfs(int pos, int sum) {
    if (pos == N)
    {
        cand[cnt++] = sum;
        return;
    }
 
    // pos위치 인덱스 값 선택O
    if (pos + Time[pos] <= N)
    {
        dfs(pos + Time[pos], sum + Pay[pos]);
    }
    // pos위치 인덱스 값 선택X
    dfs(pos + 1, sum);
 
}
 
int main() {
    input();
 
    dfs(0, 0);
 
    for (int i = 0; i < cnt; i++)
    {
        Max = max(cand[i], Max);
    }
    printf("%d\n", Max);
 
    return 0;
}