[SWEA] #1952 _ 수영장

[수영장] https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

우선, use_month 벡터에 수영장을 이용하는 달을 저장해준다.

처음 min_val의 값은 1년치 이용 금액으로 초기화 시켜주고,

dfs를 이용하여 이용하는 달의 가능한 경우(일, 월, 3개월)를 모두 계산하였다.

 

3달 금액을 계산할 때는,

예를 들어 1, 3, 5, 6, 7을 이용한다고 가정하면 모든 경우의 수를 고려하여 계산할 때,

3월에 3개월 이용 금액을 지출하는 경우 5월의 경우의 수는 무시하여 pay에 계산하지 않는다.

 

[ 소스 코드 ]

#include <cstdio>
#include <vector>
#include <algorithm>
#define DAY 0
#define MON 1
#define MON_3 2
#define YEAR 3

using namespace std;

int pay_info[4], plan[12], chk[12];
int min_val;
vector<int> use_month;

void solve(int idx, int pay);
void getPay();
int main() {
	int T;
	
	scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		scanf("%d %d %d %d", &pay_info[DAY], &pay_info[MON], &pay_info[MON_3], &pay_info[YEAR]);
		for (int j = 0; j < 12; j++) {
			scanf("%d", &plan[j]);
			if (plan[j] > 0) use_month.push_back(j);
		}
		
		if (use_month.size() == 0) {
			printf("#%d %d\n", i, 0);
			continue;
		}

		min_val = pay_info[YEAR];
		for(int j = 0; j < 3; j++) solve(0, j);
		use_month.clear();

		printf("#%d %d\n", i, min_val);
	}

	return 0;
}

void solve(int idx, int pay) {
	for (int i = 0; i < 3; i++) {
		chk[idx] = pay;
		if (idx >= use_month.size() - 1) {
			getPay();
			return;
		}
		solve(idx + 1, i);
	}
}

void getPay() {
	int total_pay = 0;

	for (int i = 0; i < use_month.size(); i++) {
		switch (chk[i]) {
		case DAY:
			total_pay += (plan[use_month[i]] * pay_info[DAY]);
			break;
		case MON:
			total_pay += pay_info[MON];
			break;
		case MON_3:
			total_pay += pay_info[MON_3];
			int cmp_mon = use_month[i];
			while (1) {
				if (i >= use_month.size() - 1) break;
				else if (use_month[i + 1] < cmp_mon + 3) i++;
				else break;
			}
			break;
		}
	}

	min_val = min(min_val, total_pay);
}