[모의 SW 역량테스트] 수영장

문제 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq

SW Expert Academy

풀이 

* 완탐으로 해결 가능

=>  월을 기준으로 모든 조합을 다 구한다. 

* 먼저 1년은 모든 월을 커버할 수 있기 때문에 최소값으로 1년 요금으로 정한다. 

* 1일과 1달은 '한' 달을 기준으로 보기 때문에 idx+1 로 월을 하나만 늘려주고, 3달은 idx+3으로 3달 후를 보도록 한다. 

1일은 그 달에 수영장을 이용한 횟수만큼 요금을 더해주며 최소값을 구한다. 

 

 

#include <iostream> #include <vector> #include <cstring> #define INF 987654321 using namespace std; bool chk[13]; int voucher[5]; int dayInMonth[13]; int ans; int min(const int &a, const int &b) { if (a > b) return b; return a; } void dfs(int idx, int res) { if (idx >= 13) { //다 돌림 ans = min(ans, res); return; } chk[idx] = true; dfs(idx + 1, res + voucher[1] * dayInMonth[idx]); dfs(idx + 1, res + voucher[2]); for (int j = idx + 1; j < idx + 3; j++) { if (j <= 12) chk[j] = true; } dfs(idx + 3, res + voucher[3]); for (int j = idx + 1; j < idx + 3; j++) { if (j <= 12) chk[j] = false; } chk[idx] = false; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for (int tc = 1; tc <= t; tc++) { memset(chk, 0, sizeof(chk)); for (int i = 1; i <= 4; i++) cin >> voucher[i]; for (int i = 1; i <= 12; i++) cin >> dayInMonth[i]; ans = voucher[4]; //1년 이용권 dfs(1, 0); cout << "#" << tc << " " << ans << '\n'; } return 0; }