[BAE/<JOON> 문제풀이] 13302. 리조트

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

13302번: 리조트

핵심::
DP 점화식

풀이::
DP[이용시간][쿠폰개수] = 최소가격 
이용권 종류가 총 3가지이므로 각각의 이용권마다 배열로 정보를 만들면 편리하다.

쿠폰을 사용하는 행동도 이용권으로 보고 쿠폰 -3개를 얻어 하루를 이용할 수 있는 가격 0원의 이용권으로 등록했다.

바텀-업 방식으로 풀이 했으므로 최대 쿠폰 개수를 알아야 DP 배열을 만들 수 있는데, 그냥 대충 100개 짜리 배열로 만들고 90개 까지만 검사했다.

최대 쿠폰 개수는 100 / 5 * 3 해서 60개 아래일 것이다.

이용권 총 4가지를 검사하며 다음과 같이 계산한다.

dp[현재 날짜][현재 쿠폰] = dp[현재 날짜 - 현재 이용권 사용 가능 일수][현재 쿠폰 - 현재 이용권 쿠폰 증정 개수] + 현재 이용권 가격

단, 만약 현재 날짜가 이용 불가 날짜라면, 이전 날짜와 비교하여 더 작은 값으로 넣어준다. -> 이 부분에서 막혔는데, 이용 불가능한 날짜의 총 가격이 그 다음날의 이용 가능한 날짜의 총 가격보다 저렴한 경우가 있다는 사실을 간과했다.

의견::
골드 4인데 정올 문제라 그런가 어려웠음

 

코드::

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int pd[4] = { 1, 3, 5, 1 };
int cpd[4] = { 0, 1, 2, -3 };
int ppt[4] = { 10000, 25000, 37000, 0 };

int main() {
	int n, m; cin >> n >> m;
	vector<int> arr(n + 1);
	vector<vector<int>> dp(n + 1, vector<int>(100, 2100000000)); 
	for (int i = 0; i < m; i++) {
		int rd; cin >> rd;
		arr[rd] = 1;
	}	

	dp[0][0] = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= 90; j++) {
			for (int k = 0; k < 4; k++) {
				if (j - cpd[k] < 0 || i - pd[k] < 0) continue;
				if (dp[i - pd[k]][j - cpd[k]] == 2100000000) continue;
				int s1 = dp[i - pd[k]][j - cpd[k]] + ppt[k];
				dp[i][j] = dp[i][j] < s1 ? dp[i][j] : s1;
				if (arr[i] == 1) {
					dp[i][j] = dp[i - 1][j] < dp[i][j] ? dp[i - 1][j] : dp[i][j];
				}
			}
		}		
	}

	int mn = 2100000000;
	for (int i = 0; i <= 90; i++) {
		mn = mn < dp[n][i] ? mn : dp[n][i];
	}

	cout << mn << "\n";

	return 0;
}