[소프트웨어 익스퍼트 아카데미][SWEA][모의 SW 역량테스트][ C++][1952번]수영장

DFS를 이용하여 풀 수 있는 문제였습니다.

 

 

#include<iostream>
#include<memory.h>
#include<algorithm>
using namespace std;
 
int price[5]; //하루 한달 3달 1년
int year[13];
int ans;
bool visited[13];
 
void dfs(int start,int temp_ans) {
    if (start > 12) {
        if (temp_ans > price[4]) {
            temp_ans = price[4];
        }
        ans = min(ans, temp_ans);
        return;
    }
    if (price[1] * year[start] < price[2]) {
        dfs(start + 1, temp_ans + price[1] * year[start]);
    }
    else
        dfs(start + 1, temp_ans + price[2]);
    dfs(start + 3, temp_ans + price[3]);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;
    scanf("%d", &T); 
    //cin >> T;
    for (int t = 1; t <= T; t++) {
        ans = 987654321; memset(visited, false, sizeof(visited));
        for (int i = 1; i < 5; i++) {
            scanf("%d", &price[i]);
            //cin >> price[i];
        }
        for (int i = 1; i < 13; i++) {
            scanf("%d", &year[i]);
            //cin >> year[i];
        }
        dfs(1, 0);
        cout <<"#"<<t<<" "<< ans<<endl;
    }
    
}