백준[14501] - 퇴사

문제

백준 14501 문제 보기

접근 방법

진료 스케줄이 주어졌을때 선택할 수 있는 경우는 두 가지가 있다. 진료를 하던가 아니면 해당 날짜에 진료를 하지않던가 이렇게 두가지 경우에 대해서 완전 탐색을하면 정답을 출력할 수 있다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int N, ans = 0;
int day[16];
int price[16];

void dfs(int date, int cost) {
    if(date > N) {
        return;
    }
    if(date == N) {
        ans = max(ans, cost);
        return;
    }
    dfs(date + 1, cost);
    dfs(date + day[date], cost+price[date]);
}

int main() {
    cin >> N;
    for(int i = 0; i < N; i ++) {
        cin >> day[i];
        cin >> price[i];
    }

    // 진료 X
    dfs(1, 0);
    // 진료 O
    dfs(day[0], price[0]);

    cout << ans;
    return 0;
}