1952번 수영장

백트래킹, 다이나믹 프로그래밍 문제다.

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq#none

<정답 코드 : 백트래킹>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int usable[12] = { 0, };
 
int price[4] = { 0, };
 
int ans = 987654321;
 
void DFS(int month, int cost)
{
    if (month >= 12)
    {
        ans = min(ans, cost);
        return;
    }
 
    // 1일
    DFS(month + 1, cost + price[0] * usable[month]);
    
    // 1달
    DFS(month + 1, cost + price[1]);
    
    // 3개월
    DFS(month + 3, cost + price[2]);
 
    // 1년
    DFS(month + 12, price[3]);
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        memset(usable, 0, sizeof(usable));
 
        for (int i = 0; i < 4; i++)
        {
            scanf("%d", &price[i]);
        }
 
        for (int i = 0; i < 12; i++)
        {
            scanf("%d", &usable[i]);
        }
 
        DFS(0, 0);
 
        printf("#%d %d\n", tc, ans);
 
        ans = 987654321;
    }
 
    return 0;
}

<정답 코드 : 다이나믹 프로그래밍>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int C[5] = { 0, };
int U[13] = { 0, };
int dp[13] = { 0, };
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        for (int i = 1; i <= 4; i++)
        {
            scanf("%d", &C[i]);
        }
 
        for (int i = 1; i <= 12; i++)
        {
            scanf("%d", &U[i]);
        }
 
        for (int i = 1; i <= 12; i++)
        {
            int ret = 987654321;
 
            ret = min(ret, dp[i - 1] + C[1] * U[i]);
            ret = min(ret, dp[i - 1] + C[2]);
 
            if (i >= 3) ret = min(ret, dp[i - 3] + C[3]);
            
            dp[i] = ret;
        }
 
        int ans = min(dp[12], C[4]);
 
        printf("#%d %d\n", tc, ans);
    }
 
    return 0;
}