[백준] 14501번 퇴사 C++ 코드

코드

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,x,y, dp[17][1003]; // 상태값은 day와 value 2가지
pair<int,int> a[17];

int go(int day, int value) {
    if(day >= n + 1) return 0;
    if(dp[day][value] != -1) return dp[day][value];
    int &ret = dp[day][value];
    int include = 0;
    // 일을 하는 경우
    if(day + a[day].first <= n + 1) {
        include = go(day + a[day].first, value + a[day].second) + a[day].second;
    }
    일을 하지 않고 제외하는 경우
    int exclude = go(day + 1, value);

    ret = max(include, exclude);
    return ret;
}

int main() {
    cin >> n;
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i < n + 1; i++) {
        cin >> x >> y;
        a[i] = {x,y};
    }
    cout << go(1,0) << '\n';
    return 0;
}

풀이

day와 value 2가지를 상태값으로 두고 dp테이블을 구성했다. 일을 하는 경우와 하지 않는 경우로 나눠서 비교를 했고, 일을 하는 경우에는 day에 일하는 데 소요되는 시간을 더해주었다. 그리고 value에는 돈을 더해주었고(인덱스 증가) include 값에도 돈을 더해주었다. 일을 하지 않는 경우에는 day를 1 증가시켜주었다.