[SWEA] 1952. [모의 SW 역량테스트] 수영장(자바/dfs)

출력

각 이용권의 요금과 각 달의 이용 계획이 입력으로 주어질 때,
가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 그 비용을 정답으로 출력하는 프로그램

 

문제 해결 방법

1년의 경우 dfs를 탐색할 필요가 없으므로, dfs 탐색을 돌기 전에 1년 비용을 미리 세팅합니다.

dfs 탐색은 달을 기준으로 탐색하게 되며, 1일, 1달, 3달을 기준으로 돌게 됩니다.

12월까지이므로 cnt가 13이 되었을 때가 기저 조건이 됩니다. 이때 최소 비용을 갱신하며 결과값을 도출하게 됩니다.

 

 

//package swea.p1952;

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

public class Solution {
	private static int[] months;
	private static int[] price;
	private static int result;


	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		for (int test_case = 1; test_case <= T; test_case++) {
			price = new int[4];// 이용권 가격들

			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < price.length; i++) {
				price[i] = Integer.parseInt(st.nextToken());
			}

			months = new int[13];// 12개월 이용 계획
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i < months.length; i++) {
				months[i] = Integer.parseInt(st.nextToken());
			}

			result = price[3];// 1년 이용권으로 세팅

			solve(1, 0);
			
			sb.append("#").append(test_case).append(" ").append(result).append("\n");
		}
		System.out.println(sb);
	}

	static void solve(int cnt, int cost) {
		if (cnt >= 13) {
			result = Math.min(result, cost);
			return;
		}

			
		int month = months[cnt];
		if(month == 0) {
			solve(cnt+1, cost);
		}else {
			// 1일 이용권
			solve(cnt+1, cost + price[0] * month);
			
			// 1달 이용권
			solve(cnt+1, cost + price[1]);
			
			// 3달 이용권
			solve(cnt+3, cost + price[2]);			
		}
			
		
	}

}
/*
1
10 40 100 300   
0 0 2 9 1 5 0 0 0 0 0 0
 * */