[14501] 퇴사

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

이번 문제는 퇴사이다.

앞으로 퇴사할 날이 주어지고

퇴사 전까지의 일과 비용이 주어졌을 때

최대한 뽕 뽑고 퇴사할 경우 얼마를 벌 수 있냐고 묻는 문제이다.

딱 봐도 DP문제인 것 같아서 DP로 풀었다.

그 날 일을 선택하느냐 그냥 넘어가느냐 두 가지로 나누어 주고 최대 값을 구해주면 된다.

끝.

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[20], n;
pair<int, int> arr[20];
int func(int num){
    if(num > n) return -987654321;
    int &ret = dp[num];
    if(ret != -1) return ret;
    ret = 0;
    return ret = max(func(num+1), func(num+arr[num].first)+arr[num].second);
}
int main(){
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        int t, p;
        scanf("%d %d", &t, &p);
        arr[i] = {t, p};
    }
    memset(dp, -1, sizeof(dp));
    printf("%d\n", func(0));
 
    return 0;
}