(C++) - 백준(BOJ) 13302번 : 리조트

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

13302번: 리조트

Top-Down dp문제였습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n, m;
int d[101][101];
bool b_day[101];//검은날(수영이 쉬는 날)설정용 배열
 
//경우의 수
//1.하루 이용권 쓸 경우
//2.연속 3일권 쓸 경우
//3.연속 5일권 쓸 경우
//4.수영이 쉬는날
 
//현재날 : day, 남은 쿠폰 : coupon, ret은 가격
int resort(int day,int coupon) {
    //쿠폰은 몇장이 남았는지 상관이 없다. 
    //루프 탈출은 방학날이 끝났으면 ㅂㅂ
 
    //먼저 기저값 설정
    if (day >= n+1) return 0;
 
    int &ret = d[day][coupon];
 
    //메모이제이션
    if (ret != -1) return ret;
 
    //쉬는날이면 아무것도 하지않는다.
    if (b_day[day]) {
        ret = resort(day + 1, coupon);
    }
    else {
        ret = 0x3f3f3f3f;
        //하루 이용권
        ret = min(ret, resort(day + 1, coupon) + 10000);
        //연속 3일권
        ret = min(ret, resort(day + 3, coupon + 1) + 25000);
        //연속 5일권
        ret = min(ret, resort(day + 5, coupon + 2) + 37000);
 
        //쿠폰 3장 이상이면 쿠폰을 하루 이용권으로 교환 비용:0원
        if (coupon >= 3) {
            ret = min(ret, resort(day + 1, coupon - 3));
        }
    }
    return ret;
}
int main() {
    cin >> n >> m;
    while(m--){
        int x;
        cin >> x;
        b_day[x] = true;
    }
    memset(d, -1, sizeof(d));
 
    cout << resort(1, 0) <<'\n';
}