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

1) 생각

12달 동안의 월별 수영장 이용 일 수와 1일, 1달, 3달, 12달 이용권의 가격이 주어진다. 최소한의 금액으로 수영장을 다닐 수 있겠끔 최소 금액을 출력하여라.

처음 생각

DFS를 이용해서 1일 1달과 한달은 idx+1을 3달은 idx+3을 1년은 idx+12를 하여 idx가 12보다 크거나 같아지면 해당 값까지의 sum 값의 최소값을 구하였다.

다음 생각

위의 방식으로는 대다수의 case는 통과하였지만 1개가 통과되지 않았다. 3달을 구할 때 무작정 더하면 안됐던 것이다. 세달 연속 이용 일 수가 모든 달이 0 0 0 이면 이용하지 않아도 되기 때문에 해당 조건을 추가해주었다. 

마찬가지로 달마다의 금액도 해당 달의 이용일 수가 0보다 클 경우에만 더해주었다.

2) 방안

1) 재귀를 이용한 DFS로 풀이를 하였다.(1 조건씩 따져가면서 나아가는 Case이기 때문에)

import java.io.IOException;
import java.util.Scanner;
 
public class Solution {
    static int n;
    static int[] pay,month;
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for(int i=1;i<=tc;i++) {
            pay = new int[4];
            month = new int[12];
            for(int j=0;j<4;j++)
                pay[j] = sc.nextInt();
            for(int j=0;j<12;j++)
                month[j] = sc.nextInt();
            result = Integer.MAX_VALUE;
            solve(0,0);
            System.out.println("#"+i+" "+result);
        }
    }
    // 1일, 1달, 3달, 1년
    private static int result;
    private static void solve(int idx,int sum) {
        if(idx>=12) {
            result = Math.min(result, sum);
            return;
        }
        
        // 1일
        solve(idx+1,sum+(month[idx]*pay[0]));
        // 1달
        if(month[idx]>0)
            solve(idx+1,sum+pay[1]);
        // 3달
        if(idx<=9) {
            if(month[idx]+month[idx+1]+month[idx+2]>0)
                solve(idx+3,sum+pay[2]);
        }
        // 1년
        if(idx==0)
            solve(idx+12,sum+pay[3]);
    }
}