코드 복사/붙여넣기 하는 당신이 아름답습니다.

13302 : 리조트

풀이

다이나믹 프로그래밍!

dp[i][j] = i번째 날에 쿠폰 개수가 j인 경우의 수!

룰루랄라

코드

#include <bits/stdc++.h>
using namespace std;

const int n_ = 100 + 10;
const int price[] = { 0,10000,25000,37000 };

const int INF = 987654321;

int n, m;
int dp[n_][n_ * 2];
bool chk[n_];

void upd(int i, int j, int v) {
	if (dp[i][j] > v || dp[i][j] == INF) dp[i][j] = v;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a;
		scanf("%d", &a);
		chk[a] = true;
	}

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n * 2; j++)
			dp[i][j] = INF;

	dp[0][0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i * 2; j++) {
			if (dp[i][j] == INF) continue;
			if (chk[i + 1]) upd(i + 1, j, dp[i][j]);
			if (j >= 3) upd(i + 1, j - 3, dp[i][j]);

			upd(i + 1, j, dp[i][j] + price[1]);
			for (int k = 1; k <= 3; k++)
				upd(i + k, j + 1, dp[i][j] + price[2]);
			for (int k = 1; k <= 5; k++)
				upd(i + k, j + 2, dp[i][j] + price[3]);
		}
	}

	int ans = INF;
	for (int j = 0; j < n * 2; j++)
		ans = min(ans, dp[n][j]);

	printf("%d", ans);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-03-06 15:05

Read more posts by this author