SWEA 1952. [모의 SW 역량테스트] 수영장 (JAVA)

SWEA 1952. [모의 SW 역량테스트] 수영장 (JAVA)

문제

알고리즘 분류

• 메모이제이션
• 그리디
• dfs

풀이

메모이제이션 dp를 활용하는 경우 각 과정에서 최소값을 저장하고 갱신 조건에 따라 최솟값을 갱신한다.

dfs를 활용하는 경우 모든 경우를 탐색하며 조건을 만족하는 경우 최솟값 갱신

코드

// 메모이제이션
public class Solution {

    public static void main(String[] args) throws Exception {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

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

        for (int t = 1; t <= T; t++) {
            int[] price = new int[4];
            int[] use = new int[13]; // dp를 활용하기 위해 1번 인덱스 부터 시작

            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int i = 0; i < 4; i++) {
                price[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(in.readLine());
            for (int i = 1; i <= 12; i++) {
                use[i] = Integer.parseInt(st.nextToken());
            }

            int[] dp = new int[13];
            for (int i = 1; i <= 12; i++) {
                int DAY = dp[i - 1] + use[i] * price[0]; // 이전 단계 최솟값 + 일 단위 요금
                int MONTH = dp[i - 1] + price[1]; // 이전 단계 최솟값 + 월 단위 요금
                int MONTH3 = (i >= 3) ? dp[i-3] + price[2] : Integer.MAX_VALUE; // 이전 단계(3개월 전) 최솟값 + 3개월 단위 요금
                int YEAR = (i == 12) ? price[3] : Integer.MAX_VALUE; // 연 단위 요금
                dp[i] = Math.min(DAY, Math.min(MONTH, Math.min(MONTH3, YEAR))); // 각 단계에서의 최솟값 갱신
            }

            sb.append("#").append(t).append(" ").append(dp[12]).append("\n"); // 최종 최솟값 반환
        }

        out.write(sb.toString());
        out.close();
    }

}

// dfs
public class Solution2 {

    static int min;
    static int[] price;
    static int[] use;

    public static void main(String[] args) throws Exception {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

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

        for (int t = 1; t <= T; t++) {
            price = new int[4];
            use = new int[12]; // dfs를 활용하기 위해 0번 인덱스 부터 시작

            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int i = 0; i < 4; i++) {
                price[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(in.readLine());
            for (int i = 0; i < 12; i++) {
                use[i] = Integer.parseInt(st.nextToken());
            }

            min = price[3]; // 최초 최솟값은 연단위 요금
            dfs(0, 0); // 0부터 시작

            sb.append("#").append(t).append(" ").append(min).append("\n");
        }

        out.write(sb.toString());
        out.close();
    }

    private static void dfs(int idx, int sum) {
        if (idx >= 12) { // 종료조건
            min = Math.min(min, sum); // 최솟값 반환
            return;
        }
        // 각각 모든 과정 탐색
        dfs(idx + 1, sum + use[idx] + price[0]); // 일 단위 요금 합산
        dfs(idx + 1, sum + price[1]); // 월 단위 요금 합산
        dfs(idx + 3, sum + price[2]); // 3개월 단위 요금 합산
    }

}