13302번 리조트

https://www.acmicpc.net/problem/13302

dp 캐시 cache 메모이제이션 다이나믹 동적계획

각각의 경우에 따라 구현

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 111
#define INF 2e9
 
int n, m, dp[Max][Max];
bool rest[Max];
 
int simulation(int day, int cp)
{
    if (day > n) {
        return 0;
    }
 
    int &ret = dp[day][cp];
 
    if (ret != -1) {
        return ret;
    }
 
    ret = INF;
 
    // 갈 수 없는 날
    if (rest[day]) {
        ret = min(ret, simulation(day + 1, cp));
    }
 
    // 5일
    ret = min(ret, simulation(day + 5, cp + 2) + 37000);
 
    // 3일
    ret = min(ret, simulation(day + 3, cp + 1) + 25000);
 
    // 하루
    ret = min(ret, simulation(day + 1, cp) + 10000);
    
    // 쿠폰
    if (cp >= 3) {
        ret = min(ret, simulation(day + 1, cp - 3));
    }
 
    return ret;
}
 
int main()
{
    cin.tie(0);
 
    memset(dp, -1, sizeof(dp));
 
    scanf("%d %d", &n, &m);
    
    int input;
    for (int i = 0; i < m; i++) {
        scanf("%d", &input);
        rest[input] = true;
    }
 
    printf("%d\n", simulation(1, 0));
 
    return 0;
}