1952 수영장

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

1~12월까지의 수영장 이용 계획이 있고 1일, 1달, 3달, 1년 이용권의 요금이 주어질 때, 모든 이용 계획을 커버하는 최소 비용을 구하는 문제이다. 재귀함수를 적절히 설계해서 모든 경우를 찾아서 그 중 최소값을 구하면 된다.

go(now,cost) = 현재 위치가 now이고 지금까지 쓴 비용이 cost

ans의 초기값을 1년 이용권으로 두고

1. 1일 이용권 사용시 cost에 해당 월 (now) 이용 날짜 * 1일 이용권 사용비용을 더해주고 위치를 1 더한다.

2. 1달 이용권 사용시 cost에 1달 이용권 사용비용을 더해주고 위치를 1 더한다.

3. 3달 이용권 사용시 cost에 3달 이용권 사용비용을 더해주고 위치를 3 더한다.

now가 12 이상이 되면 ans과 비교를 통해 현재 cost가 더 작으면 갱신하고 함수를 종료한다.

#include <cstdio>
#include <algorithm>
using namespace std;
 
int t,c[4],p[12],ans;
 
void go(int now,int cost)
{
    if(now>=12) { ans=min(ans,cost); return; }
    go(now+1,cost+c[0]*p[now]); // 1일 이용권 사용
    go(now+1,cost+c[1]); // 1달 이용권 사용
    go(now+3,cost+c[2]); // 3달 이용권 사용
}
 
int main()
{
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        for(int i=0;i<4;i++) scanf("%d",&c[i]);
        for(int i=0;i<12;i++) scanf("%d",&p[i]);
        ans=c[3];
        go(0,0);
        printf("#%d %d\n",k,ans);
    }
    return 0;
}