[SWEA] 1952. 수영장

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE

SW Expert Academy

---

import java.util.Scanner;

class Solution {
	
	static int[] cost = new int[4];
	static int[] month = new int[13];
	static int answer;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for(int i=0; i<T; i++) {
			for(int j=0; j<4; j++) cost[j] = sc.nextInt();
			for(int j=1; j<=12; j++) month[j] = sc.nextInt();
			
			answer = cost[3];
			recur(1, 0);
			System.out.println("#" + (i+1) + " " + answer);
		}
	}
	public static void recur(int cur, int sum) {
		if(cur >= 13) {
			answer = Math.min(answer, sum);
			return;
		}
		
		if(month[cur] == 0) {
			recur(cur+1, sum);
		} else {
			recur(cur+1, sum+(month[cur]*cost[0]));
			recur(cur+1, sum+cost[1]);
			recur(cur+3, sum+cost[2]);
		}
		
	}
}

---

1년의 각각 월마다 수영장 이용계획과 1일, 1달, 3달, 1년 이용권 가격이 주어질 때 가장 적은 비용 수영장을 이용할 수 있는 비용을 구하는 문제입니다. 저는 처음에 모든 월마다 이용할 수 있는 모든 이용권 가격을 넣어서 각각의 비용을 계산하려고 했는데 아이디어가 떠오르지 않아서 검색하다보니 재귀적으로 완전탐색하여 간단하게 구현할 수 있는 문제였습니다. 이런 문제에서는 무조건 모든 경우의 수를 대입하여 구하려고 하지말고 재귀적으로 구하는방법도 한번 생각해야 겠고, 재귀함수에 좀 더 익숙해져야 겠다고 생각했습니다.

[문제 풀이]

1. cost 에 각 이용권의 가격을 입력받습니다. 0 번째 인덱스부터 차례대로 1일, 1달, 3달, 1년 이용권 가격이 들어가게 됩니다.

2. month 에 각 달의 수영장 이용계획을 넣습니다. 저는 0 번째 인덱스를 버리고 1 번째 달부터 12 번째 까지 입력하기 위해서 길이를 13으로 잡았습니다.

3. 1년 이용권 가격을 초기값으로 넣어줍니다.

4. 재귀적으로 모든 경우를 탐색하기 위해서 recur함수를 실행하는데 month 의 인덱스 1부터 시작하기 때문에 recur(1, 0)을 호출합니다.

5. recur 함수를 설명 해 보자면

① month 의 크기를 13으로 잡았기 때문에 현재의 달을 나타내는 cur 이 13보다 커지게 되면 더해진 비용값 sum을 최솟값 비교해서 answer에 저장합니다.

② 만약에 month[cur] 이 0이라면 수영장 이용계획이 없다는 뜻이므로 cur을 1 더해줘서 다음달로 넘어갑니다.

③ recur(cur+1, sum + (month[cur]*cost[0]) 은 1일 이용권을 사용하므로 이용계획에 1일 이용권의 가격을 더해줍니다.

④ recur(cur+1, sum+cost[1]) 은 1달 이용권을 사용하는 것이므로 1달 이용권의 가격을 더해줍니다.

⑤ recur(cur+3, sum+cost[2]) 는 3달 이용권을 사용하는 것이므로 3달 이용권의 가격을 더해주고 3을 cur에 더해줍니다.