백준 13302 : 리조트 (C++)

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

 

처음엔 N이 100 이하인 것을 보고 백트래킹을 생각했다. 

 

그러나 곧 시간 초과가 날 것을 알았는데, 

왜냐하면 매일 일일 이용권/3일 이용권/5일 이용권/쿠폰 사용의 4지선다를 선택하므로,

약 4^100 번의 계산이 필요할 것이기 때문이다.

 

그리고 또 다른 해법으로 DP를 떠올렸다.

처음엔 

int dp[현재 일 수][3일권 잔여일 수][5일권 잔여일 수][보유 쿠폰 개수]

이런식으로 dp 배열을 복잡하게 짜는 것을 고려했는데, 천천히 생각해보면 그럴 필요가 없다.

 

풀어 말하자면, 이 문제에서는 5일권이 하루 남은 상황에서 3일권을 산다던가, 

4일 연속으로 리조트를 이용하고자 하면 5일권을 산다던가,

이런 이용권 사용기간이 겹치는 상황을 고려할 필요가 없다.

 

가격 책정을 잘 보면,

애매하게 4일이 남았다면 5일권보다는 3일권 + 하루 이용권을 사는 것이 이득이고,

2일이 남았다면 3일권보다는 하루 이용권을 2번 사는 것이 이득이다.

 

5일권을 쓰고 나면 그 뒤에 2일이 남는 경우, 그걸 고려해서 3일권을 산다던가 할 필요가 없다.

 

따라서, dp 배열도 저렇게 복잡하게 짤 필요 없이 단순화할 수 있다.

int dp[현재 일자][보유 쿠폰 개수]

 

 

따라서 [현재 일자]를 for문으로 1 씩 올려가면서 바텀업 식으로 dp를 갱신하되,

리조트를 사용할 수 없는 날은 이전 dp값을 그대로 쓰는 방식으로 구현해주면 된다.

 

소스 코드:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define INF 1000000

int N, M;
bool canUse[106];
int ret = 0;
int dp[106][202]; // [현재 일자][쿠폰 개수]

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	fill(canUse, canUse + 106, true);
	
	for (int i = 0; i < 106; i++)
		for (int j = 0; j < 202; j++)
			dp[i][j] = INF;

	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int input;
		cin >> input;
		canUse[input] = false;
	}

	// base case
	dp[0][0] = 0;

	for (int i = 0; i <= N; i++)
	{
		for (int j = 0; j < 202; j++)
		{
			if (!canUse[i + 1])
			{
				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
			}
			else
			{
				// 1일권
				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 10000);

				// 쿠폰 사용
				if (j >= 3)
					dp[i + 1][j - 3] = min(dp[i + 1][j - 3], dp[i][j]);
			}

			// 3일권
			dp[i + 3][j + 1] = min(dp[i + 3][j + 1], dp[i][j] + 25000);

			// 5일권
			dp[i + 5][j + 2] = min(dp[i + 5][j + 2], dp[i][j] + 37000);
		}
	}

	int ret = INF;
	for (int i = 0; i < 202; i++)
	{
		ret = min(ret, dp[N][i]);
	}
	cout << ret;
}