[SWEA 1952] 수영장 (Java)

SWEA 1952 수영장

문제풀이

가장 저렴하게 구매하는 방법!? 뭔가 DP의 향이나는 문제설명이다. 하지만 조건을 봤을 때 12개월만 생각하면 된다. 완전탐색으로 모든 경우를 다 살펴봐도 될거 같다!

다음과 같은 4가지 경우가 있다.

• 이용하지 않는 월에는 구매하지 않아도 된다. 하지만 구매해도 된다.
  • 두 번째 테스트 케이스에서 이 경우를 찾을 수 있다. 이용 횟수가 없더라도 1개월 또는 3개월 이용권을 구매하는게 전체적으로 보았을 때 더 저렴할 수 있다. 삼성은 테스트 케이스가 친절해서 너무 좋다.
• 1일 이용권으로 이번 달 사용 횟수를 모두 구매한다.
• 1개월 이용권을 구매한다.
• 3개월 이용권을 구매한다. (10월 까지만 구매 가능)

구현코드

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

public class Solution {
	
	static int[] cost;
	static int[] plan;
	static int T, ans;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		T = Integer.parseInt(br.readLine());
		
		for(int t = 1 ; t <= T ; ++t) {
			cost = new int[4];
			plan = new int[13];
			
			st = new StringTokenizer(br.readLine());
			for(int i = 0 ; i < 4 ; ++i) cost[i] = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine());
			for(int i = 1 ; i <= 12 ; ++i) plan[i] = Integer.parseInt(st.nextToken());
		
			ans = cost[3];
			dfs(1, 0);
			
			System.out.println("#" + t + " " + ans);
		}
	}

	private static void dfs(int month, int total) {
		if(month == 13) {
			ans = ans > total ? total : ans;
			return;
		}
		
		// 이용안할 때 안사기 
		if(plan[month] == 0) dfs(month + 1, total);
		
		// 1일 사용권으로 채우기 이용횟수 1회 이상 
		if(plan[month] > 0) dfs(month + 1, total + plan[month] * cost[0]);
		
		// 1달 사용권으로 채우기
		dfs(month + 1, total + cost[1]);
		
		// 3달 사용권으로 채우기  10월까지만 구매가능
		if(month <= 10) dfs(month + 3, total + cost[2]);
	}
}