[Algorithm]Baekjoon 13302번 :: 리조트

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

 

 

 

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int maxNum = 0x3f3f3f3f;
int n, m;
bool days[101] = { false };
int dp[101][26] = { 0 };
 
int DFS(int index, int couponCount)
{
    if (index >= n) return 0;
    if (dp[index][couponCount] != 0x3f3f3f3f) return dp[index][couponCount];
 
    int result = 0x3f3f3f3f;
 
    if (days[index+1]) // 다음날이 리조트 안가는날이면
    {
        result = DFS(index + 1, couponCount);
    }
    else
    {
        // 1일권짜리
        result = DFS(index + 1, couponCount) + 10000;
 
        // 3일권짜리
        result = min(result, DFS(index + 3, couponCount + 1) + 25000);
 
        // 5일권짜리
        result = min(result, DFS(index + 5, couponCount + 2) + 37000);
 
        if (couponCount >= 3) // 쿠폰이 있다면 사용
        {
            result = min(result, DFS(index + 1, couponCount - 3));
        }
    }
 
    return dp[index][couponCount] = result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        int num;
        cin >> num;
        days[num] = true;
    }
 
    memset(dp, 0x3f, sizeof(dp));
 
    cout << DFS(0, 0);
}

 

최소의 비용을 구하는 문제이다.

1일짜리, 3일짜리, 5일짜리에 대해 각 선택에 대해서 dp테이블을 업데이트해줘야하는데, '쿠폰'이라는 개념이 추가됐기 때문에 이 부분을 반영해서 작성해야 한다.

이 쿠폰개수가 각 루트의 독립성을 보장한다는것을 인지해야 한다.

 

추가적으로 리조트를 안가는날에는 그냥 그대로 넘기면 된다. 

혹시나 아닌 경우도 있나 싶었는데, 통과하는거보니 그렇진 않나보다.