[1952] 수영장

풀이

dp[i]는 i월 째까지 다닐 때 가장 적게 다닐 수 있는 비용

dp[i] = min(a,b,c,d)

1. a : dp[i-1] + i월을 1일권으로 다니는 경우
2. b : dp[i-1] + i월을 1달권으로 다니는 경우
3. c : dp[i-3] + i-2,i-1,i월을 3달권으로 다니는 경우
4. d : 1년권으로 다닌 경우

코드

#include <cstdio>

using namespace std;
int main(void) {
	int tcase = 0; scanf("%d", &tcase);
	for (int tc = 1; tc <= tcase; tc++) {
		int ans = 0xFFFFFFF;
		int dp[13] = { 0, };
		int cost[4] = { 0, };
		int plan[13] = { 0, };
		for (int i = 0; i < 4; i++) {
			scanf("%d", &cost[i]);
		}
		for (int i = 1; i <= 12; i++) {
			scanf("%d", &plan[i]);
		}
		for (int i = 1; i <= 12 ; i++) {
			int temp[3] = { -1,-1,-1 };
			if (plan[i] == 0) {
				dp[i] = dp[i - 1];
				continue;
			}
			temp[0] = dp[i - 1] + plan[i] * cost[0];
			temp[1] = dp[i - 1] + cost[1];
			if (i >= 3) temp[2] = dp[i - 3] + cost[2];
			int t = 0xFFFFFFF;
			for (int k = 0; k < 3; k++) {
				if (temp[k] == -1) continue;
				t = t > temp[k] ? temp[k] : t;
			}
			dp[i] = t;
		}
		ans = dp[12] > cost[3] ? cost[3] : dp[12];
		printf("#%d %d\n", tc, ans);
	}
	return 0;
}