백준13302 리조트

작성일 | In

문제 링크

  • http://icpc.me/13302

문제 출처

  • 2016 KOI 전국 본선 초등부3, 고등부1

사용 알고리즘

  • DP

시간복잡도

  • O(n2)

풀이

먼저, dp[i][j]를 i일에 쿠폰 j개가 있을 때의 정답이라고 정의합니다.
정답을 찾는 함수를 solve라 하고, 매개 변수를 day, coupon, price로 잡습니다. 이 매개 변수는 각각 현재 날짜, 쿠폰 개수, 현재 누적 비용을 나타냅니다.
적절히 탐색을 하면서 메모이제이션을 수행하면 됩니다.
코드에서 주석으로 설명을 이어가겠습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> v(110);
int dp[110][110];

int solve(int day, int coupon, int price){
	if(n < day) return price; //범위 초과 시 현재 가격 반환
	if(dp[day][coupon]) return dp[day][coupon] + price; //이미 탐색했을 경우
	if(v[day]) return solve(day+1, coupon, price); //불가능한 날짜면 다음날을 탐색

	int ans = (1<<31)-1;
	ans = min(ans, solve(day+1, coupon, price+10000)); //1일권 구매
	ans = min(ans, solve(day+3, coupon+1, price+25000)); //3일권 구매 + 쿠폰 1개
	ans = min(ans, solve(day+5, coupon+2, price+37000)); //5일권 구매 + 쿠폰 2개

	if(coupon >= 3){ //쿠폰 사용 가능 시
		ans = min(ans, solve(day+1, coupon-3, price));
	}

	dp[day][coupon] = ans - price;
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i=0; i<m; i++){
		int t; cin >> t; v[t] = 1;
	}
	cout << solve(1, 0, 0);
}