[SWEA] 1952 수영장

🔔 문제

수영장 1952번

🎯 풀이방법

달마다 고려해야 되는 경우

• 1일 이용권으로 모든 사용 횟수 구매하기
• 1달 이용권 구매
• 3달 이용권 구매 (10월까지 사용가능, 사용 후 3개월 후로 이동)
• 이번 달 이용계획이 없으면, 이용권 구매 X or 구매 O 선택.

다음 예시의 최소 이용금액은 어떻게 구할까?

정답은 바로 아래와 같다. 바로 이용계획이 없더라도 3개월 이용권을 구매하는 게 전체적으로 저렴할 수 있다.

💡 이 문제를 통해 얻어갈 것

완전탐색 (dfs) 문제

💻 Java code

20,820 kb 메모리, 119 ms 실행시간, 1,894 B 코드길이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {
    static int dayFee, monthFee, threeMonthFee, yearFee;  // 요금
    static int answer;
    static int[] schedule = new int[13];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for(int t=1; t<=T; t++) {
            // 입력
            st = new StringTokenizer(br.readLine());
            dayFee = Integer.parseInt(st.nextToken());
            monthFee = Integer.parseInt(st.nextToken());
            threeMonthFee = Integer.parseInt(st.nextToken());
            yearFee = Integer.parseInt(st.nextToken());

            // 초기화
            answer = yearFee;

            //1월 ~ 12월
            st = new StringTokenizer(br.readLine());
            for(int i=1; i<=12; i++) {
                schedule[i] = Integer.parseInt(st.nextToken());
            }

            // 최소 비용 구하기
            dfs(1, 0);
            sb.append("#"+t+" "+answer+"\n");
        }
        System.out.println(sb.toString());
    }

    public static void dfs(int month, int total) {
        if(month == 13) {
            answer = answer>total ? total:answer;
            return;
        }

        // 이용 안 할 때 안사기
        if(schedule[month] == 0)
            dfs(month+1, total);

        // 1일 사용권으로 채우기 : 이용횟수 >= 1
        if(schedule[month] > 0)
            dfs(month+1, total+schedule[month]*dayFee);

        // 1달 사용권으로 채우기
        if(schedule[month] > 0)
            dfs(month+1, total+monthFee);

        // 3달 사용권으로 채우기 10월까지만 구매 가능
        if(month <= 10)
            dfs(month+3, total+threeMonthFee);
    }
}