[SW Expert] [모의 SW 역량테스트] 1952번 수영장 (Java)

SW Expert [모의 SW 역량테스트] 1952번 수영장 :

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

 

 

나는 이 문제를 dfs로 풀었지만, 풀이 후 다른 사람의 코드를 보니 DP로 푼 경우가 많았다.

DP로는 각 단계마다 비용의 최솟값을 구하는 방식으로 푸는 듯 하다.

 

입력을 받을 때 1일치로 결제를 하는 것과 한 달을 결제하는 것 중에 작은 값을 배열에 저장한다.

그 뒤 dfs로 각각의 달에 어떤 방식으로 결제를 할지 선택한다.

결제 방식을 선택했다면 이용권 가격을 곱해서 총 비용을 계산해주면 된다.

 

총 걸린 시간 : 30분

난이도 : ★★☆☆☆

 

코드

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

public class Main {
    private static int answer;
    private static int[] cost = new int[4];
    private static int[] plan = new int[12];
    private static byte[] check = new byte[12];

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

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            answer = Integer.MAX_VALUE;

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < 4; i++) { // 이용권 가격 입력
                cost[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            int days;
            for (int i = 0; i < 12; i++) { // 이용 계획 입력
                days = Integer.parseInt(st.nextToken());
                plan[i] = Math.min(days * cost[0], cost[1]);
            }

            dfs(0, 0);
            answer = Math.min(answer, cost[3]);
            System.out.println("#" + t + " " + answer);
        }
    }

    private static void dfs(int index, int cnt) {
        if (index == 12) {
            check();
            return;
        }
        if (cnt == 3) cnt = 0;
        if (0 <= cnt && cnt < 3) {
            check[index] = 3;
            dfs(index + 1, cnt + 1);
        }
        if (cnt == 0) {
            check[index] = 1;
            dfs(index + 1, cnt);
        }
    }

    private static void check() {
        int index = 0, price = 0;
        while (index < 12) {
            switch (check[index]) {
                case 1:
                    price += plan[index];
                    index++;
                    break;
                case 3:
                    price += cost[2];
                    index += 3;
                    break;
            }
        }
        answer = Math.min(price, answer);
    }
}