[백준] 13302 - 리조트

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

13302번: 리조트

 

이 문제는 처음에 쿠폰을 3장 이상 가질 수 없다고 생각해서 낭패를 보았다.

그래서 dp배열을 100 x 3으로 설정해서 제대로 된 답이 나오지 않았고, 이후에

dp[i][j] (i <= 100, j <= 100) = i번째 날에 j개의 쿠폰을 가지고 있을 때 지불할 최소 금액으로 정의하였다.

 

경우의 수가 좀 있다.

 

1. 리조트에 가지 못하는날
   • 그날을 아예 없애버린다. 그래서 dp[i][j] = dp[i + 1][j]
2. 리조트에 갈 수 있는 날
   • 하루 이용권을 끊는다. dp[i][j] = dp[i + 1][j] + 10
   • 3일 이용권을 끊는다. 여기서 쿠폰 1개가 지급된다. dp[i][j] = dp[i + 3][j + 1] + 25
   • 5일 이용권을 끊는다. 여기서 쿠폰 2개가 지급된다. dp[i][j] = dp[i + 5][j + 2] + 37
   • 지금 가지고 있는 쿠폰이 3개 이상이다. 쿠폰을 3개를 사용하고 해당 날짜에 리조트에 간다. dp[i][j] = dp[i + 1][j - 3]

 

#include <iostream>
using namespace std;

int n, m, a[101], dp[101][101];

int go(int day, int coupon) {

	if (day > n) return 0;
	if (dp[day][coupon]) return dp[day][coupon];

	int ret = 1000000000;

	if (a[day]) ret = go(day + 1, coupon);
	else {
		ret = min(ret, go(day + 1, coupon) + 10);
		ret = min(ret, go(day + 3, coupon + 1) + 25);
		ret = min(ret, go(day + 5, coupon + 2) + 37);
		
		if (coupon >= 3) ret = min(ret, go(day + 1, coupon - 3));
	}

	return dp[day][coupon] = ret;
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int c; cin >> c;
		a[c] = 1;
	}

	cout << go(1, 0) * 1000;
}