Boj 13302 c++ 리조트

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

 

리조트를 갈 수 있는 날과 갈 수 없는 날이 주어졌을 때 이용권 및 쿠폰을 사용하여 

리조트에 머물 수 있는 최소 비용을 구하는 문제이다.

 

각각의 이용권의 비용 및 효용은 다음과 같다.

하루 이용권	10,000원	없음
연속 3일권	25,000원	쿠폰 1장
연속 5일권	37,000원	쿠폰 2장

 

 

리조트에 머무는 최대 일수는 100일이다 .

 

고로, 나올 수 있는 가장 큰 비용은 100만원이다.

여기서 적절히 3일권과 5일권을 이용하여 비용을 줄일 수 있다.

 

쿠폰의 용도 또한 고려해봐야 한다.

3일권과 5일권을 구매하였을 때 각각 1장, 2장을 제공해주는데, 3장을 모으면 하루 이용권과 교환할 수 있다.

 

이제 정답을 구하기 위한 dp 테이블을 설계해보자.

dp배열의 정의는 i번째 날에서 쿠폰이 j개 있을 때의 최소비용이 가장 적당할 것 같다.

 

하지만 쿠폰의 용도를 반영하여 점화식을 작성하는 방법이 떠오르지 않았고, 

특정 일수에서 보유할 수 있는 쿠폰의 개수가 제각각이기에 불가능한 경우를 제외시킬 방법 또한 떠오르지 않았다.

 

하지만 이는 dp[0 ~ 100][0 ~ 최대 쿠폰 개수 ] 값을 모두 inf 로 업데이트 해준 뒤, 

dp[0][0] 만을 0으로 초기화하면 해결되는 문제였다. 어차피 최소비용을 구하기 위해서는 min을 사용해야 하고, 

불가능한 경우는 inf이기 때문에 반영되지 않는다. 때문에, dp[0][0]에서 시작하여 새롭게 업데이트된 값들만이 반영되는 것이다.

 

리조트가 휴일인 날은 비용 없이 넘겨주고, 이용권을 사용해야 하는 날에만 1일권, 3일권, 5일권을 적절히 사용해준다.

3일권, 5일권을 사용한 경우에는 쿠폰 수 또한 업데이트 해준다.

쿠폰 수가 3개 이상인 경우에는 쿠폰을 사용하여 하루를 지낼 수 있기에, 이 또한 쿠폰 수를 반영하여 업데이트 해준다.

 

모든 경우는 최소를 보장해야 하기에 min을 사용해주어야 한다.

 

정답은 마지막 날 중에서 쿠폰 수 별로 순회하며 최솟값만을 출력해주면 된다.

 

 

전체 코드

#include <iostream>
#define Max 1000001
using namespace std;
int dp[105][55]; // i일차에 쿠폰이 j개 있을 때 최소비용
int N, M, ans = Max;
int holiday[105]; // 휴일을 0으로, 갈 수 있는 날을 1로
int main() {
    cin >> N >> M;

    for(int i = 1; i <= N; i++) {
        holiday[i] = 1;
    }

    for(int i = 1; i <= M; i++) {
        int idx;
        cin >> idx;
        holiday[idx] = 0;
    }

    for(int i = 0; i <= 100; i++) {
        for(int j = 0; j <= 50; j++) {
            dp[i][j] = Max; //불가능한 경우는 제외하기 위한 테크닉
        }
    }
    dp[0][0] = 0;
    for(int i = 1; i <= N+1; i++) {
        for(int j = 0; j <= 50; j++) {
            if(holiday[i] == 0) {        //그대로 넘겨주기
                dp[i][j] = min(dp[i][j], dp[i-1][j]);
            } else {
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 10000); //1일권

                for(int k = 1; k <= 3; k++) {   //3일권 사용시
                    dp[i-1+k][j+1] = min(dp[i-1+k][j+1], dp[i-1][j] + 25000);
                }
                for(int k = 1; k <= 5; k++) {
                    dp[i-1+k][j+2] = min(dp[i-1+k][j+2], dp[i-1][j] + 37000);
                }
                if(j >= 3) {
                    dp[i][j-3] = min(dp[i][j-3], dp[i-1][j]);
                }
            }
        }
    }

    for(int i = 0; i <= 50; i++) {
        ans = min(ans, dp[N][i]);
    }
    cout << ans;
}

 

 

2차원 dp 설계를 조금 더 연습해봐야겠다.