[Java] swea 1952 수영장

[Java] swea 1952 수영장

 

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE&problemTitle=sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

 

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

public class 모의SW_1952_수영장 {
	
	static int[] prices = new int[4];
	static int[] myPlan = new int[12];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		for (int testcase = 1; testcase <= T; testcase++) {
			MIN = Integer.MAX_VALUE;
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < 4; i++) {
				prices[i] = Integer.parseInt(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < 12; i++) {
				myPlan[i] = Integer.parseInt(st.nextToken());
			}
			
			MIN = prices[3];
			solve(0, 0);
			
			System.out.println("#" + testcase + " " + MIN);
		} // tc
		
		
	} // main

	static int MIN;
	private static void solve(int curMonth, int cost) {
		if(cost >= MIN) return;
		if(curMonth >= 12) {
			if(MIN > cost) MIN = cost;
			return;
		}
		
		solve(curMonth+1, cost + (myPlan[curMonth] * prices[0]));
		solve(curMonth+1, myPlan[curMonth] == 0? cost : cost+prices[1]);
		solve(myPlan[curMonth] == 0? curMonth+1 : curMonth+3, myPlan[curMonth] == 0? cost :cost + prices[2]);
		
	} // solve
}

 

옛날엔 못풀었었나...? 한참 뒤에 풀었었나..? 그랬었던 문제..

 

일종의 DP느낌...? 인 듯..???

 

1월부터 시작해서 (난 인덱스를 0부터 잡아서 0~11이다.) 12월까지

각 달에 1일권, 1달권, 3달권 모두 시도해본다.

 

 이 때 1년 이용권 한 번 사용하는 것을 MIN 금액으로 둔다.

 

1일권을 사용하는 경우 그 달의 이용날 * 1일권 금액을 더해서 재귀 month+1 해서 한 번 호출.

1달권을 사용하는 경우 그 달의 이용날이 0일이라면 금액이 더해지지 않고 그냥 month+1 해서 호출.

                               그 달의 이용날이 1일 이상이라면 금액에 1달권금액을 더하고 month+1 해서 호출.

3달권을 사용하는 경우 그 달의 이용날이 0일이라면 3달권 사용하지 않고 그냥 month+1 해서 호출.

                               그 달의 이용날이 1일 이상이라면 3달권금액더하고 month+3 해서 호출.

 

그러니까 함수 한 번 호출에 3번의 재귀를 들어간다.

 

종료 조건은 month가 12가 될 떄 ! (0~11 이므로) 

그 때의 cost 를 MIN과 비교하여 MIN을 업데이트하면 된다.

 

이 때!! 함수 처음 호출할 때 cost 와 MIN을 비교하여 이미 cost가 MIN과 같거나 크다면  불필요한 진행이므로 그냥 return 하여 더이상 함수진행을 막는다!