[ 백준 13302 ] 리조트 (C++)

백준의 리조트(13302) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

리조트를 갈 수 없는 날을 제외하고, 모든 날에 리조트를 간다고 했을 때, 리조트에 입장하기 위한 최소의 비용을

구해야 하는 문제이다.

본인은 메모이제이션을 이용해서 이 문제를 접근해보았다. 구체적으로는 깊이우선탐색기법인 DFS탐색과

동적계획법(Dynamic Programming) 을 합쳐서 구현해보았다.

먼저, 본인이 사용한 변수부터 알아보자.

int Price[][] 라는 int형 2차원 배열을 하나 사용해주었는데, 이 변수의 의미부터 알아보자.

변수의 인덱스에는 '날짜'와 '쿠폰의 갯수' 가 들어가게 된다.

즉, Price[날짜][쿠폰의갯수] 라 생각하고 구현하였는데, 구체적인 의미는 다음과 같다.

Price[a][b] = c 의 의미는 "a번째 날, b개의 쿠폰을 가지고 있을 때, 리조트에 들어가는데 들어가는 최소비용은

c원입니다."

를 의미한다.

DFS의 매개변수에는 날짜와 Coupon의 갯수 2개의 매개변수를 사용해서 호출해 주었다.

최소 비용을 구해야 하기 때문에 초기의 Price[][] 배열값은 모두 무한대로 초기화 해주었다.

메모이제이션을 이용해서 구현했기 때문에, 이미 계산된 (날짜, 쿠폰의 갯수)에 대해서는 또 다른 탐색 없이 그대로 return 해

주었다.

또 하나, 생각해줘야 할 것은 리조트에 가지 못하는 날이 존재한다는 것이다.

리조트에 가지 못하는 날은, 현재 날짜에서 + 1을 해서 DFS탐색을 호출해서 똑같이 최소비용을 구한 후 그 값을 return 시켜

주었다.

int DFS(int Day, int Coupon)
{
    if (Day > N) return 0;
    if (Price[Day][Coupon] != INF) return Price[Day][Coupon];
    if (Rest_Day[Day] == true)
    {
        Price[Day][Coupon] = DFS(Day + 1, Coupon);
        return Price[Day][Coupon];
    }
 
    Price[Day][Coupon] = Min(Price[Day][Coupon], DFS(Day + 1, Coupon) + 10000);
    Price[Day][Coupon] = Min(Price[Day][Coupon], DFS(Day + 3, Coupon + 1) + 25000);
    Price[Day][Coupon] = Min(Price[Day][Coupon], DFS(Day + 5, Coupon + 2) + 37000);
    if (Coupon >= 3) Price[Day][Coupon] = Min(Price[Day][Coupon], DFS(Day + 1, Coupon - 3));
 
    return Price[Day][Coupon];
}
 

본인이 구현한 DFS 함수이다.

line3 과 line4 에서는 더 이상의 탐색이 필요 없는 경우 그대로 적절한 값을 return 해준다.

line5 는 '리조트에 입장하지 못하는 날' 에 대한 처리이다.

line 11 ~ 13 에서 본격적으로 최소비용을 구하게 된다.

리조트를 이용할 때는 '하루이용권', '연속 3일권', '연속 5일권' 을 이용해서 입장할 수 있으므로 이 3가지 경우에 대해서

모두 최소비용을 구해서 그 중 최소비용을 Price[][] 배열에 저장해 주었다.

line 14를 보게되면, '쿠폰이 3장 이상 있을 경우'에 대한 처리이다.

쿠폰이 3장은 하루 이용권 한장으로 별도의 추가비용없이 리조트를 이용할 수 있다.

만약, 현재 쿠폰이 3장 이상이라면, 이 쿠폰을 이용해서 리조트를 이용하는 방법에 대해서도 계산해 주었다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 110
#define INF 987654321
using namespace std;
 
int N, M;
int Price[MAX][MAX];
bool Rest_Day[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a; cin >> a;
        Rest_Day[a] = true;
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j <= N; j++)
        {
            Price[i][j] = INF;
        }
    }
}
 
int DFS(int Day, int Coupon)
{
    if (Day > N) return 0;
    if (Price[Day][Coupon] != INF) return Price[Day][Coupon];
    if (Rest_Day[Day] == true)
    {
        Price[Day][Coupon] = DFS(Day + 1, Coupon);
        return Price[Day][Coupon];
    }
 
    Price[Day][Coupon] = Min(Price[Day][Coupon], DFS(Day + 1, Coupon) + 10000);
    Price[Day][Coupon] = Min(Price[Day][Coupon], DFS(Day + 3, Coupon + 1) + 25000);
    Price[Day][Coupon] = Min(Price[Day][Coupon], DFS(Day + 5, Coupon + 2) + 37000);
    if (Coupon >= 3) Price[Day][Coupon] = Min(Price[Day][Coupon], DFS(Day + 1, Coupon - 3));
 
    return Price[Day][Coupon];
}
 
void Solution()
{
    int Answer = DFS(1, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}