백준 13302(리조트) c++

문제

13302번: 리조트

n일의 여름방학이 주어지고, m번의 바쁜날이 주어지면 여름방학동안 리조트 이용을 바쁜날을 제외하고 매일 할 떄

최소비용을 구하는 문제입니다. 위의 표의 첫번째 행은 여름방학의 날을 의미합니다. 검은색은 바쁜날입니다.

두번째 행과 세번째 행은 각각 비용입니다. 두번째 행은 7만원이 들고, 세번째 행은 62000원이 들어서 최소비용은 62000원입니다.

쿠폰을 3개 모으면 하루 이용권이 무료로 제공됩니다.

 

쿠폰의 여부에 따라 최소비용을 결정하는 것이 까다로웠습니다.

그래서 dp와 모든 경우의 수를 탐색하는 dfs 방법을 결합해 사용했습니다.

먼저 price 배열을 만들어 주었습니다.

price[i][j] = i번째 날 j개의 쿠폰을 가지고 있는 상황에서 리조트를 이용하는데 최소 비용입니다.

int n, m;
int price[101][101];
bool rest[101]; //바쁜날은 true

cin >> n >> m;
for (int i = 0; i < m; i++)
{
    int a;
    cin >> a;
    rest[a] = true;
}
for (int i = 1; i <= n; i++)
  for (int j = 0; j <= n; j++)
     price[i][j] = INF;

먼저 n과 m을 입력받고 m개의 바쁜날을 입력받아 rest배열에 true로 설정해 줍니다.

그리고 최소비용으로 dp를 진행할 것이므로 모든 price배열을 INF(20억)으로 초기화 해줍니다.

int dfs(int day, int coupon)
{
    if (day > n)
        return 0;
    if (price[day][coupon] != INF)
        return price[day][coupon];
    if (rest[day])
    {
        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 부분입니다. 매개변수로 day와 coupon으로 설정합니다.

첫번째 if문은 day가 여름방학의 날짜 n을 넘어갈 때입니다 이때는 그냥 0을 return합니다.

두번째 if문은 메모이제이션 기법으로 이미 업데이트된 값은 INF가 아닐 것이므로 그대로 return합니다.

세번째 if문은 현재 날짜가 바쁜날이면 어차피 현재 리조트를 이용하지 못하므로 그대로 day만 +1을 해 진행해 줍니다.

나머지 밑의 코드들은 현재 day기준으로 하루이용권, 연속 3일권, 연속 5일권을 이용했을 때, 최소값을 dfs로 진행합니다.

진행하면서 쿠폰이 3개 이상이면 하루 이용권을 무료로 이용가능하므로 day를 +1해주고, coupon을 -3해줍니다.

---

전체 코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#define INF 2000000000
using namespace std;
using ll = long long;
int n, m;
int price[101][101];
bool rest[101];
int dfs(int day, int coupon);
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a;
        cin >> a;
        rest[a] = true;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++)
            price[i][j] = INF;

    int ans = dfs(1, 0);
    cout << ans;

    return 0;
}
int dfs(int day, int coupon)
{
    if (day > n)
        return 0;
    if (price[day][coupon] != INF)
        return price[day][coupon];
    if (rest[day])
    {
        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];
}