백준 14501. 퇴사

문제출처 : baekjoon online judge

14501번: 퇴사

이 문제는 전형적인 다이나믹프로그래밍 문제입니다.

각 날짜마다 일했을 때, 구할 수 있는 최대 이윤과 그 날 일하지 않고 다음 날 일했을 때 최대 이윤을 비교하는 방식입니다.

각 날짜마다 걸리는 시간을 고려해서, 일 할 수 없으면 0으로 설정해서 다음 날 일했을 때 이윤과 비교합니다.

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
int cache[20];
 
int t[20];
int p[20];
 
int n;
 
int dp(int x) {
    if (x > n)
        return 0;
 
    int &ret = cache[x];
 
    if (ret != -1)
        return ret;
 
    if (x + t[x] - 1 > n)
        return ret = max(0, dp(x + 1));
 
 
    return ret = max(dp(x + 1), p[x] + dp(x + t[x]));
}
 
int main() {
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> p[i];
    }
 
    memset(cache, -1, sizeof(cache));
 
    dp(1);
 
    int answer = 0;
 
    for (int i = 1; i <= n; i++) {
        answer = max(answer, cache[i]);
    }
 
    cout << answer << endl;
}

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!