BOJ 14501번 퇴사

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/14501/14501/%EC%86%8C%EC%8A%A4.cpp

 

임의의 오늘(today)부터 일을 시작하여 걸리는 시간(arr[today][0])이 만약 총날짜(N) 보다 같거나 작다면

나는 오늘(today)부터 일해도 되는 것이고, 일이 끝난 today+arr[today][0] 의 날짜부터 일을 재개하면 된다.

결국 첫시작일인 1일부터 N일이 주어지면 1부터 N일까지 할 수 있는 모든 경우를 탐색하여 최대를 찾으면 된다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
#pragma warning(disable:4996)
 
int N;
int arr[16][2];
 
int ans(int today) {
    if (today > N) return 0;
 
    int temp = 0;
    if (today + arr[today][0] - 1 <= N)
        temp = ans(today + arr[today][0]) + arr[today][1];
 
    temp = max(temp, ans(today + 1));
    return temp;
}
 
int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d%d", &arr[i][0],&arr[i][1]);
    }
 
    printf("%d", ans(1));
    return 0;
}