[JAVA][SWEA][모의SW] 1952번 수영장 이용요금

 

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

문제의 출처

SW Expert Academy

[제약 사항]

1. 시간 제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초
2. 모든 종류의 이용권 요금은 10 이상 3,000 이하의 정수이다.
3. 각 달의 이용 계획은 각 달의 마지막 일자보다 크지 않다.

[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 1일 이용권의 요금, 1달 이용권의 요금, 3달 이용권의 요금, 1년 이용권의 요금이 순서대로 한 칸씩 띄고 주어진다.
그 다음 줄에는 1월부터 12월까지의 이용 계획이 주어진다.

 

정답코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

import javax.annotation.Generated;

public class Solution{
	static int N;
	static int L;
	static int price[]=new int[4];
	static int plan[]=new int[13];
	static int answer;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int T=Integer.parseInt(st.nextToken());
		for(int test_Case=1;test_Case<=T;test_Case++) {
			st=new StringTokenizer(br.readLine());

			for(int i=0;i<4;i++) {
				price[i]=Integer.parseInt(st.nextToken());
			}
			st=new StringTokenizer(br.readLine());
			for(int i=1;i<13;i++) {
				plan[i]=Integer.parseInt(st.nextToken());
			}
			answer=price[3];
			dfs(0,1);
			System.out.printf("#%d ",test_Case);
			System.out.println(answer);
		}
	}
	
	private static void dfs(int money,int month) {
        		if(money>price[3]) {
			return;
		}
		if(month>12) {
			if(answer>money) {
				answer=money;		
			}
			return;
		}
		if(plan[month]==0) {
			dfs(money,month+1);
		}else {
			dfs(money+plan[month]*price[0],month+1);
			dfs(money+price[1],month+1);
			dfs(money+price[2],month+3);
		}
	}
}