[BOJ] 13302 : 리조트

#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;
}