[SWEA 1952 - Java] 수영장

SW Expert Academy

 

풀이

 

이 문제는 1~12월까지만 확인을 하고 이용권이 종류도 매우 적기 때문에 모든 경우를 확인해도 시간초과가 되지 않습니다!

따라서 저는 월을 기준으로 재귀를 호출하며 답을 구했습니다.

 

1. answer 변수에 1년 이용권 가격을 넣어준 후 재귀 호출을 시작합니다.
2. 1월 부터 시작하여 해당 월에 1일 이용권, 1달 이용권, 3달 이용권을 이용하는 경우들에 대해 재귀를 호출합니다.
   • 이 때 해당 월에 수영장 출석 계획이 없다면 이용권을 결제하지 않도록 합니다.
3. 1~12월 까지의 이용권 금액이 모두 추가된 후엔 answer의 값과 현재 까지의 요금을 비교하여 현재 요금이 더 작은 경우 answer를 업데이트 해줍니다.

import java.util.Scanner;

public class Solution {
	static int day;
	static int oneMon;
	static int threeMon;
	static int year;
	static int[] plan = new int[13];
	static int answer;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();

		for(int tc=1; tc<=T; tc++) {
			day = sc.nextInt();
			oneMon = sc.nextInt();
			threeMon = sc.nextInt();
			year = sc.nextInt();

			for(int i=1; i<=12; i++) {
				plan[i] = sc.nextInt();
			}

			// 1년 단위 등록 
			answer = year;

			dfs(1, 0);

			System.out.println("#"+tc+" "+answer);
		}

	}

	static void dfs(int month, int cost) {
		
		if(month > 12) {
			if(cost < answer)
				answer = cost;
			return;
		}

		//이번달에 이용함 
		if(plan[month] > 0) {
			//1일 이용권
			dfs(month+1, cost + day * plan[month]);

			//1달 이용권
			dfs(month+1, cost+oneMon);
			
			//3달 이용권
			dfs(month+3, cost+threeMon);
		}
		
		//이용안함 
		else {
			dfs(month+1, cost);
		}
		
	}

}