[SWEA] 1952번 : 수영장

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

문제

 

입력

 

출력

 

 

---

소스코드

import java.io.*;
import java.util.*;

class Solution {
    static int arr[], price[];
    static ArrayList<Integer> isMonth;
    static int result;

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

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            price = new int[4];
            price[0] = Integer.parseInt(st.nextToken());
            price[1] = Integer.parseInt(st.nextToken());
            price[2] = Integer.parseInt(st.nextToken());
            price[3] = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            arr = new int[13];
            isMonth = new ArrayList<>();
            for (int j = 1; j <= 12; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
                if (arr[j] != 0) {
                    isMonth.add(j);
                }
            }
            result = price[3];
            dfs(0, 0);
            sb.append("#" + (i + 1) + " " + result + "\n");
        }
        System.out.println(sb);
    }

    static void dfs(int idx, int sum) {
        if (idx >= isMonth.size()) {
            if (result > sum) result = sum;
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (i == 0) { // 1일
                dfs(idx + 1, sum + (price[i] * arr[isMonth.get(idx)]));
            } else if (i == 1) { // 1달
                dfs(idx + 1, sum + price[i]);
            } else if (i == 2) { // 3달
                dfs(idx + 3, sum + price[i]);
            }
        }
    }
}

 

해결 방법

1. 달마다 이용계획, 이용권 요금, 이용계획이 있는 달을 각각 배열에 저장한다.
2. DFS 탐색을 진행한다. 이용계획이 있는 달을 1일, 1달, 3달 이용하는 경우를 모두 확인한다.
3. 이용계획이 있는 달의 범위를 초과하는 경우 result와 현재 가격을 비교한다.