[삼성 SW Expert Academy] 수영장 1952[JAVA]

Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE&&&

SW Expert Academy

풀이 방법

1. 문제를 보자마자 DFS가 떠올랐다.

2. 하지만, 평소 풀던 문제와 달리 각 달마다 방문하는 횟수와 1일 기준, 1개월 기준, 3개월 기준 등 다양한 기준들로 부터 어떻게 구현해야 할지 어려웠다.

3. 1일권으로 수영장 방문일정 소화하기 -> 마지막은 한 달권으로 바꾸기 -> 세 번째 마지막은 3달 권으로 바꿔보기 

4. 1년권은 한 번 통째로 하는 것이기 때문에 dfs할 필요 없고, 따로 비교 한번 만 더해보기 

코드

import java.util.Scanner;

public class 수영장_SW1952 {

	static int Tc;
	static int[] cost;
	static int[] plan;
	static int min;
	
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		
		Tc = sc.nextInt();
		
		for( int tc=0; tc<=Tc; tc++) {
			min = Integer.MAX_VALUE;
			cost = new int[4];
			plan = new int[12];
			
			// 각 이용권 비용
			for( int i=0; i<4; i++) {
				cost[i] = sc.nextInt();
			}
			
			// 12 개월 이용 계획
			for( int i=0; i<12; i++) {
				plan[i] = sc.nextInt();
			}
			
			dfs(0,0);
			
			// 1년치는 마지막에 한번더 점검
			if ( cost[3] < min) {
				min = cost[3];
			}
			
			
			System.out.println("#"+tc+" "+min);
		}
	}
	
	private static void dfs(int month, int fee) {
		
		// 기저조건
		if ( month>=12) {
			if( fee < min ) {
				min = fee;
			}
			
			return;
		}
		
	
		// 해당 월에 계획이 없을 경우 그냥 ㄲ
		if( plan[ month ] == 0 ) {
			dfs( month+1, fee);
		} 
		else {
			// 1일 먼저 다채워주고 
			dfs( month + 1, fee + cost[0]*plan[month]);
			// 한달 다 채워주고
			dfs( month + 1, fee + cost[1]);
			// 3달 다 채워주고		
			dfs( month + 3, fee + cost[2]);
		}
		
		
	}
}