[SWEA] 1952. 수영장

1952 수영장

풀이)

DFS를 이용해서 모든 경우를 다 확인해보면 되는 문제였다.

1월에만 1년 이용권을 살 수 있고,

그 외 나머지 월에는 1일, 1달, 3달 이용권을 살 수 있는 선택지가 있다.

그 조합들을 다 확인해보면 된다.

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int cost[4];//1일, 1달, 3달, 1년
int result;
int month[13];
 
void dfs(int wal,int res) {
    if (wal > 12) {
        result = min(result, res);
        return;
    }
    if (wal == 1) {
        dfs(wal+12, res+cost[3]);
    }
    //1.1일 선택지
    dfs(wal + 1, res + month[wal] * cost[0]);
    //2.한달 선택지
    dfs(wal + 1, res + cost[1]);
    //3.세달 선택지
    dfs(wal + 3, res + cost[2]);    
}
 
 
int main() {
    //freopen("sample_input (1).txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        for (int i = 0; i < 4; i++) {
            scanf("%d", &cost[i]);
        }
        for (int i = 1; i <= 12; i++){
            scanf("%d", &month[i]);
        }
        result = 999999999;//최대로나올값 3000*31*12 < 999999999
        dfs(1, 0);
        printf("#%d %d\n", test_case, result);
    }
 
    return 0;
}