[BOJ] 백준 13302. 리조트 (Gold V)

스터디그룹에서 진행한 연습 중 A번으로 나왔던 문제.

문제가 굉장히 긴데, 실생활에서 흔히 마주칠만한 좋은 문제였다.

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

13302번: 리조트

---

의식의 흐름 및 해설

스키를 못타는 날이 중간에 껴 있더라도 이용권을 사용할 수 있어 문제 난이도가 낮아진 느낌.

만약 이런 조건이 없었다면 case_work가 좀 더 빡세졌을 것 같다.

 

N이 100이기 때문에 시간복잡도가 상당히 널널하다.

현재 날짜에 스키를 탈 수 있다면 1일권, 3일권, 5일권, 혹은 쿠폰이 3장 이상 있을 경우 쿠폰 사용을 하도록 하자.

주의할 점은, 현재 사용 가능한 가장 싼 이용권을 이용하는 그리디적으로 해결하려 한다면, 그 이후에 오히려 더 싸게 이용할 수 있는 경우를 놓치고 비싸게 이용해버릴 수 있기 때문에 dp로 해결해야 한다.

 

dp[i][j]: i번째 날까지 쿠폰 j개일 때 이용권 비용

으로 dp식을 짜자. 주의할 점은 쿠폰 보유 개수가 3개를 넘어설 수 있기 때문에 dp[MAXN][4]와 같이 잡을 경우 28점의 점수밖에 얻지 못한다.

 

knapsack 또는 sliding_window_dp와 같은 특수케이스가 아니기 때문에 탑다운이든, 바텀업이든 시간복잡도는 동일하며, 현재 날짜에 어떤 이용권을 사용하는지에 따라 다음 날짜로 상황이 넘어가므로 탑다운으로 쉽게 해결이 가능하다.

 

만약 스키를 타지 못하는 날은 바로 다음날 상황의 dp값을 리턴해버리자.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
const int MAX = 103;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, M, p[3] = { 10000, 25000, 37000 };
int d[MAX][MAX];
bool k[MAX];
int dp(int cur, int c) {
	if (cur > N)return 0;
	if (k[cur])return dp(cur + 1, c);
	int& ret = d[cur][c];
	if (ret != -1)
		return ret;
	ret = INF;
	ret = min({ ret, dp(cur + 1, c) + p[0],
		dp(cur + 3, c + 1) + p[1], dp(cur + 5, c + 2) + p[2] });
	if (c >= 3)
		ret = min(ret, dp(cur + 1, c - 3));
	return ret;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int day;
		cin >> day;
		k[day] = true;
	}
	memset(d, -1, sizeof(d));
	cout << dp(1, 0);
}

---

dp 기초로 해결하기 좋은 재밌는 문제.