SW Expert Academy 1952. 수영장

문제

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

걸린 시간

00 : 52 : 50

풀이

C++

#include <iostream>
#include <vector>
#define INF 987654321
using namespace std;

int d, m, mmm, y;
vector<int> plan(12);

int solve(int month, int fee){
    // 기저 사례
    if(month == 11) return fee;
    // 재귀 호출
    int ret = INF;
    if(month+3 <= 11) ret = min(ret, solve(month+3, fee+mmm));
    if(month+1 <= 11) ret = min(ret, solve(month+1, fee+m));
    if(month+1 <= 11) ret = min(ret, solve(month+1, fee+plan[month+1]*d));
    return ret;    
}

int main()
{
    int test_case;
    int T;
    cin >> T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        cin >> d >> m >> mmm >> y;
        for(auto& i : plan) cin >> i;
        int ans = solve(-1, 0);
        ans = min(ans, y);
        cout << "#" << test_case << " " << ans << "\n";
    }
    return 0;
}

완전 탐색으로 모든 경우의 수를 탐색하면 된다. 재귀 함수는 요금을 지불한 마지막 달 그리고 현재까지 지불한 요금을 매개인자로 갖고 진행한다.