SWEA 1952. 수영장

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

1. 문제

2. 풀이

1일 이용권, 한 달 이용권, 3개월 이용권, 연간 이용권의 4가지 경우의 수가 존재한다.
1월부터 12월까지의 모든 케이스를 고려해보자.

달마다 4가지 경우의 수의 12개월 경우의 수(중복순열)는 4^12개 = 16777216개이므로 일반적으로 시행할 수 없는 방법이다.

하지만 1년 이용권의 경우 단 한번의 경우만 존재하기 때문에 경우의 수를 줄여볼 수 있다.
이는 3^12 = 531441개의 경우의 수로 충분히 완전탐색을 할 만한 조건이다.
또한 3개월의 경우 역시 달이 줄어드므로 전체 경우가 더욱 줄어들기 때문에, 완전탐색으로 풀어볼만 한 것이다.

3. 코드

import java.util.Scanner;

public class Swim {
	static int[] cost = new int[4];
	static int[] month = new int[12];
	static int[] membership = {1, 1, 3}; //1일일때는 한달 뒤, 한달일 때도 한달 뒤, 3개월일 경우 3달 뒤로 이동
	static int answer;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt(), t = 0;
		
		while(t++ < tc) {
			answer = Integer.MAX_VALUE;
			for (int i = 0; i < 4; i++) cost[i] = sc.nextInt();
			for (int i = 0; i < 12; i++) month[i] = sc.nextInt();
			
			
			solve(0,0);
			System.out.println("#" + t + " " + Math.min(answer, cost[3])); //계산값과 1년값 비교
		}

	}
	private static void solve(int cnt, int sum) {
		if (sum > answer) return;
		if (cnt >= 12) {
			answer = Math.min(answer, sum);
			return;
		}
		
		for (int i = 0; i < 3; i++) {
			solve(cnt + membership[i], sum + ((i == 0) ? cost[i] * month[cnt] : cost[i]));
		}
	}
	

}