[SWEA] 모의 SW 역량 테스트 :: 1952번 수영장 자바(java) 풀이

sw expert academy 1952번 수영장 자바(java) 풀이

• 모의 SW 역량테스트 수영장
• sw expert academy 1952번 수영장
  
  
  

문제정리

1. 이용권
   1일 이용권 : 하루 이용
   1달 이용권: 한달 이용. 매달 1일 부터 시작
   3달 이용권: 3달 이용. 매달 1일 시작.
   1년 이용권: 매년 1월 1일 시작
2. 각 이용권의 요금과 각 달의 이용계획이 주어진다.
3. 가장 적은 비용으로 수영장을 이용할 수 있는 방법과 그 비용을 출력해라
   
   
   

문제풀이

이 문제는 완전탐색 문제입니다. 탐색해야 하는 경우도 많지 않습니다.
1년 이용권의 경우는 한 번만 검사하면 되기 때문에 마지막에 따로 한 번만 검사합니다.
재귀를 통해 모든 경우를 탐색하고 그 달의 이용일이 0인 경우 비용을 더해주지 않으면 됩니다

    dfs(cnt+1, sum + (months[cnt]*fee[0])); // 하루 이용
    dfs(cnt+1, sum + fee[1]);   // 한 달 이용
    dfs(cnt+3, sum + fee[2]);   // 세 달 이용

위와 같이 재귀를 통해 모든 경우를 탐색할 수 있습니다.
문제에 나온 예제를 가지고 설명드리겠습니다.
직접 디버깅 해보시는게 이해가 빠를 수 있습니다.

10 40 100 300
0 0 2 9 1 5 0 0 0 0 0 0

1. 3,4,5,6월 모두 하루 이용하는 경우로 먼저 탐색하게 됩니다. 그리고 min값을 갱신합니다.
2. 다시 6월(cnt: 5)로 돌아와서 그 밑에 dfs문인 한 달이용으로 들어갑니다.
3. 계산하고 돌아와서 3번째 dfs문으로 들어가 3달 이용으로 하고 3달 이용이기 때문에 +3을 해줍니다.
4. 6월 달에 대해서 모든 경우를 따져보았기 때문에 5월 달로 돌아와 2번째 dfs문을 실행해 5월달에 대해 한달 이용으로 하고 6월은 하루이용으로 합니다.
   이렇게 계속 재귀를 돌면서 모든 경우에 대해 탐색할 수 있습니다.
   이때 그 당시의 context를 기억하기 위해 sum에 더한 상태로 넘기면 안되고 위와 같이 인자로 넘길때 더해진 값을 넘겨야 합니다.
   3월에 하루이용권으로 모두 하게되면 20원 입니다.
   sum이 20인 상태로 넘기면 다시 돌아와서 한달 이용권으로 계산할때 20+40=60원으로 계산이 되기 때문입니다.
   이도 직접 디버깅 해보시면 무슨 차이인지 아실 수 있습니다.
   
   
   

모의 sw 역량 테스트 수영자 자바 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class Solution {
    static int[] fee;
    static int[] months;
    static int min;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testNum = Integer.parseInt(br.readLine());

        for(int test=1; test<=testNum; test++){
            String[] temp = br.readLine().split(" ");
            fee = new int[4];
            // 이용권 요금
            for(int i=0; i<temp.length; i++)
                fee[i] = Integer.parseInt(temp[i]);

            // 월별 이용 계획
            months = new int[12];
            temp = br.readLine().split(" ");
            for(int i=0; i<temp.length; i++)
                months[i] = Integer.parseInt(temp[i]);

            min = Integer.MAX_VALUE;
            dfs(0, 0);  // 완전 탐색
            min = min > fee[3] ? fee[3] : min;  // 1년 이용권 사용금액과 비교
            System.out.println("#" + test + " " + min);
        }
        br.close();
    }

    public static void dfs(int cnt, int sum){
        if(cnt >= 12){
            min = min > sum ? sum : min;
            return;
        }

        // 이용일 수 0인 달은 비용을 더하지 않는다
        if(months[cnt] == 0){
            dfs(cnt+1, sum);
        }
        else{
            dfs(cnt+1, sum + (months[cnt]*fee[0])); // 하루 이용권 사용
            dfs(cnt+1, sum + fee[1]);   // 한달 이용권 사용
            dfs(cnt+3, sum + fee[2]);   // 세달 이용권 사용
        }
    }
}