[SWEA] 1952번 수영장

1952번 수영장

문제 링크

 

해결방법

모든 경우를 탐색하는 완전탐색 문제이다

(+ 이 문제는 완전탐색 or DP 로 해결이 가능한 문제라고 한다)

 

 

⭐️ 솔루션 ⭐️

아래의 경우로 나누었다

• 만약 이번 달에 이용 계획이 없다면?

  • 다음 달로 넘어간다
  • 3달 이용권을 결제한다
  • 1월이라면 1년 이용권을 결제한다

• 이용 계획이 있다면?

  • 1일 이용권을 이번 달의 이용 횟수 만큼 결제한다
  • 1달 이용권을 결제한다

12달의 경우를 모두 탐색했다면 결제 비용의 최소값을 갱신한다

 

문제 조건

• 1일 이용권 : 그 달의 이용횟수만큼 결제
• 1달 이용권 : 1달 동안 사용
• 3달 이용권 : 10 ~ 12 11 ~ 12 와 같이 연도가 초과하는 경우에도 사용 가능
• 1년 이용권 : 1월의 경우에만 사용 가능

 

 

소스코드

문제 해결 시간 : 30m

메모리 : 12512 KB

시간 : 10 ms

#include <iostream>
#include <math.h>
#include <algorithm>
#define INF 987654321
using namespace std;

int testcase;
int ans,add;
int cost[4];
int plan[13];

void dfs(int month,int money){
    
    // 12월까지 모두 등록한 경우
    if(month>12){
        ans = min(ans,money);
        return;
    }
    
    // 이번 달은 수영장 이용 X
    if(plan[month] == 0){
        dfs(month+1,money);
    }else{
        // 1일 이용권으로 사용하는 경우
        add = plan[month] * cost[0];
        dfs(month+1,money+add);
        
        // 1달 이용권으로 사용하는 경우
        add = cost[1];
        dfs(month+1,money+add);
    }
    
    // 3달 이용권으로 사용하는 경우
    if(month+3 <= 12){
        add = cost[2];
        dfs(month+3,money+add);
    }else if(month+3 == 13){
        add = cost[2];
        dfs(month+3,money+add);
    }
    
    // 1년 이용권으로 사용하는 경우 (1월의 경우에만)
    if(month == 1){
        add = cost[3];
        dfs(month+12,money+add);
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=1; t<=testcase; t++){
        
        for(int i=0; i<4; i++){
            cin >> cost[i];
        }
        for(int i=1; i<=12; i++){
            cin >> plan[i];
        }
        
        ans = INF;
        dfs(1,0);
        
        cout << "#" << t << " " << ans << "\n";
    }
    
    return 0;
}