[Unsolved][JAVA] SWEA 1952 수영장

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq 

SW Expert Academy

 

1. 서론

 

간단하다면 간단한데 나는 풀이 방법을 떠올리지 못한... 그런 문제.

 

2. 문제 풀이

 

수영장에 4가지 이용권이 존재한다. 조건은 다음과 같다.

   ① 1일 이용권 : 1일 이용이 가능하다.

   ② 1달 이용권 : 1달 동안 이용이 가능하다. 1달 이용권은 매달 1일부터 시작한다.

   ③ 3달 이용권 : 연속된 3달 동안 이용이 가능하다. 3달 이용권은 매달 1일부터 시작한다.
       (11월, 12월에도 3달 이용권을 사용할 수 있다 / 다음 해의 이용권만을 구매할 수 있기 때문에 3달 이용권은 11월, 12월, 1월이나 12월, 1월, 2월 동안 사용하도록 구매할 수는 없다.)

   ④ 1년 이용권 : 1년 동안 이용이 가능하다. 1년 이용권은 매년 1월 1일부터 시작한다.

그리고 12달동안의 각 달마다 며칠을 수영장을 이용할지가 주어진다. 위의 이용권을 사용해 수영장을 이용할 수 있는 가장 적은 비용을 구하는 문제이다.

처음에는 중복순열로 뽑기를 해서 이용권을 고르고 모든 경우의 수를 계산해서 어쩌고...라고 생각했는데 역시나. 그렇게 하면 3달 이용권 때문에 코드가 말도 안 되게 어려워진다. (아닌 걸 알면서도 이외의 생각이 잘 안 났음)

결론은 재귀다. 나는 재귀가 뭔지 알지만... 코드를 잘 짜지 못한다.

재귀로 1일 이용권, 1달 이용권, 3달 이용권을 매개변수로 돌려서 종료 조건인 12월에 다다르면 최솟값을 계산해주는 식으로 계산해준다고 한다. => 생각은 해봤는데 그럼 3달은 어떻게 하지?라고 생각했는데 그냥 +3 해서 쿨하게 넘어가더라...
초기값을 1년 이용권으로 지정하면 1일, 1달, 3달 이용권을 믹스해서 사용하는 것과 1년 이용권의 값을 자동으로 비교할 수 있다.

 

3. 코드 설명

 

import java.io.*;
import java.util.*;

public class Main {
	
	static int day, month1, month3, year, ans;
	static int[] use;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for (int k = 1; k <= T; k++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			while(st.hasMoreTokens()) {
				day = Integer.parseInt(st.nextToken());
				month1 = Integer.parseInt(st.nextToken());
				month3 = Integer.parseInt(st.nextToken());
				year = Integer.parseInt(st.nextToken());
			}
			
			use = new int[13]; //1~12월
			int i = 1;
			st = new StringTokenizer(br.readLine());
			while(st.hasMoreTokens())
				use[i++] = Integer.parseInt(st.nextToken());	
			
			ans = year;
			calc(1, 0);
			sb.append("#" + k + " " + ans + "\n");
		}
		
		bw.write(sb.toString());
		bw.close(); br.close();
	}

	private static void calc(int month, int val) {
		if (ans <= val) return;
		if (month > 12) {
			if (ans > val)
				ans = val;
			return;
		}
	
		if (use[month] != 0) {
			calc(month + 1, val + Math.min(use[month] * day, month1));
			calc(month + 3, val + month3);
		}
		else 
			calc(month + 1, val);
	}
}

값들을 입력받고 calc 함수를 돌려서 값을 구한다. 이때 매개변수로 달과 현재 계산된 이용료를 저장한다.

month는 use배열의 index역할을 하는데, 즉 몇 월인지를 나타내는 지표다. 그래서 그냥 어렵게 생각할 것 없이 +3 해주면 되는 것이다.

그리고 원래는 calc(month +1, val + use[month] * day), calc(month + 1, val + month1) 이렇게 해서 각각 1일 이용권과 1달 이용권을 나타내지만 month+1 부분이 겹치므로 저렇게 둘 중 작은 값을 계산해준 후에 그 값을 사용한다!!

 

내 머리로는 낼 수 없는 아이디어였지만... 지금 이렇게 봐 두면 다음에는,,, 언젠가는 풀 수 있겠지?!