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

느낌이 딱!!!!봐도 DP인데...

모든 조합을 따져봐도 3^12이하의 시간 복잡도가 나와서 그냥 풀었다.

이 시간 복잡도가 맞는지는 모르겠지만...시간 복잡도 계산 어렵다!!!!

그래서 그냥 모든 경우의 수 중에서 최소값 출력~

#include <stdio.h>
#include <string.h>
 
int charge[4];
int month[13];
int MIN;
 
void search(int M, int T)
{
    if (M >= 13)
    {
        if (T < MIN)
        {
            MIN = T;
        }
        return;
    }
 
    int K = 0;
    for (int i = 0; i < 4; i++)
    {
        switch (i)
        {
        case 0:
            K = month[M] * charge[0];
            search(M + 1, T + K);
            break;
        case 1:
            K = charge[1];
            search(M + 1, T + K);
            break;
        case 2:
            if (M > 10)
                break;
            K = charge[2];
            search(M + 3, T + K);
            break;
        case 3:
            if (M > 2)
                break;
            K = charge[3];
            search(M + 12, T + K);
            break;
        }
    }
    return;
}
 
int main()
{
    int Test;
    scanf("%d", &Test);
 
    for (int i = 1; i <= Test; i++)
    {
        memset(charge, 0, sizeof(charge));
        memset(month, 0, sizeof(month));
        MIN = 99999999;
 
        for (int j = 0; j < 4; j++)
        {
            scanf("%d", &charge[j]);
        }
 
        for (int j = 1; j <= 12; j++)
        {
            scanf("%d", &month[j]);
        }
 
        search(1, 0);
 
        printf("#%d %d\n",i, MIN);
    }
    return 0;
}