[Java] SWEA 수영장

1. 문제분석

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

SW Expert Academy

수영장을 다니는데 1일, 한달, 세달, 1년의 요금제가 있다.

입력으로 수영장을 얼마나 이용하는지가 주어지고 주어진 요금제를 최소한으로 사용하는 방법을 구하는 문제다.

 

필자는 DFS와 DP가 떠올랐다. 항상 최선의 결과가 나올 수 없으니 모든 것을 다 탐색해야하기 때문이다.

DP는 달마다 최선을 구하기 때문에 둘 중 고민하다가 DFS를 선택했다.

 

처음 구했던 방법은 DFS를 어떻게 접근하냐 였다.

1일과 한달은 각 가격을 비교해서 더 좋은 것을 선택하도록 했지만 3달이 문제였다.

3달은 1,2,3 -> 4,5,6 ... -> 11, 12 이렇게 2가지로 구분했는데 여기서 막히게 되었다.

 

하지만 다시 생각해보자. 꼭 저렇게 계산해야 할까?

if문으로 현재 계산하는 달이 12월을 넘어가면 자동으로 처리하면 되지 않을까? 라는 생각이 들었다.

결과적으로 정리해보면 1일, 1달, 3달을 각각 DFS로 넣어 구해주는 것이다.

 

단 구하고자하는 값의 초기값을 1년 요금제로 해야한다. 어떻게 구하든 1년 요금제 이상으로 나오면 손해기 때문이다.

2. 구현

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

public class Solution {

    static int DAY, MONTH, THREE_MONTH, YEAR;
    static int[] swim = new int[13];
    static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for (int c = 1; c <= tc; c++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            DAY = Integer.parseInt(st.nextToken());
            MONTH = Integer.parseInt(st.nextToken());
            THREE_MONTH = Integer.parseInt(st.nextToken());
            YEAR = Integer.parseInt(st.nextToken());

            answer = YEAR;

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

            calc(1, 0);
            System.out.println("#" + c + " " + answer);
            answer = 0;
        }
    }

    static void calc(int month, int sum) {
        //
        if (answer <= sum) {
            return;
        }
        if (month > 12) {
            answer = Math.min(answer, sum);
            return;
        }
        if (swim[month] == 0) {
            calc(month + 1, sum);
        } else {
            calc(month + 1, sum + (DAY * swim[month]));
            calc(month + 1, sum + MONTH);
            calc(month + 3, sum + THREE_MONTH);
        }
    }
}

 

생각보다 단순하게 DFS를 구현했다. 만약 구하고자하는 달에 수영을 안하면 그냥 패스, 아니면 구하면 된다.

3. 마무리

DFS라는걸 알았는데.. 왜 구현을 못했을까..

0인경우는 그냥 넘기면 되는데 왜 상세한 필터까지 생각했을까...