[백준] 퇴사 14501번 (C++)

출처 : 14501번: 퇴사 (acmicpc.net)

14501번: 퇴사

풀이 방법

일을 할지 안 할지 선택하면 되는 dp 문제이다

문제의 입력을 받은데로 인덱스가 시작일 이므로 문제는 간단하다

다음 날 일을 시작하면  p[day]+Money(day + t[day]) 그냥 넘기려면 Money(day+1)을 해주어서 둘 중 max를 선택하면 된다.

#include <iostream>
#include <algorithm>
#include <memory.h> 

using namespace std;
const int MAX = 15 + 1;
const int INF = 987654321;

int N;

int cache[MAX];
int t[MAX];
int p[MAX];

int Money(int day)
{
    //기저 사례 상담 진행하는 일 수가 N을 초과하면 안 된다
    if (day == N + 1)
        return 0;
    if (day > N + 1)
        return -INF;
    int& result = cache[day]; // cache 연결 하는 부분
    if (result != -1) {        
        return result;
    }        
    result = 0;
    //해당 일 상담을 택할 것인가 다음날 상담으로 넘어갈 것인가
    result = max(Money(day + 1), p[day] + Money(day + t[day]));
    return result;
}



int main(void)
{
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> t[i] >> p[i];
    memset(cache, -1, sizeof(cache));
    cout << Money(1) << endl;

    return 0;

}