[SWEA] #1952 - 수영장

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

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

SW Expert Academy

 

💡 문제

---

[설명]

김 프로는 수영장을 이용한다.

김 프로는 지출이 너무 많아 내년 1년 동안 각 달의 이용 계획을 수립하고 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 있다.

수영장에서 판매하고 있는 이용권은 아래와 같이 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일부터 시작한다.

각 달의 이용 계획은 [Table 1]의 형태로 수립된다.

1월

2월

3월

4월

5월

6월

7월

8월

9월

10월

11월

12월

이용 계획

0일

0일

2일

9일

1일

5일

0일

0일

0일

0일

0일

0일

[Table 1]

이용 계획에 나타나는 숫자는 해당 달에 수영장을 이용할 날의 수를 의미한다.

각 이용권의 요금과 각 달의 이용 계획이 입력으로 주어질 때,

가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 그 비용을 정답으로 출력하는 프로그램을 작성하라.


[예시]

수영장에서 판매하는 1일 이용권, 1달 이용권, 3달 이용권, 1년 이용권의 요금은 각각 10원, 40원, 100원, 300원이다.

이때 수영장을 이용할 수 있는 방법은 [Table 2]와 같이 다양한 경우를 생각할 수 있다.

 

이용하는 방법	이용권	비용
1번 경우) 모두 1일 이용권으로만 이용한다.	1일 이용권 17개 : 17 * 10원 = 170원	170원
2번 경우) 모두 1달 이용권으로만 이용한다.	1달 이용권 4개 : 4 * 40원 = 160원	160원
3번 경우) 3월은 1일 이용권으로 이용하고 4월, 5월, 6월은 3달 이용권으로 이용한다.	1일 이용권 2개, 3달 이용권 1개 : 2 * 10원 + 1 * 100원 = 120원	120원
4번 경우) 3월과 5월은 1일 이용권으로 이용하고 4월과 6월은 1달 이용권으로 이용한다.	1일 이용권 3개, 1달 이용권 2개 : 3 * 10원 + 2 * 40원 = 110원	110원
5번 경우) 1년 이용권으로 이용한다.	1년 이용권 1개 : 1 * 300원 = 300원	300원

[Table 2]

다른 경우도 가능하지만, 가장 적은 비용으로 수영장을 이용한 경우는 4번 경우이다.

따라서, 정답은 110이 된다.

 

💡 아이디어

---

완전 탐색을 이용하면 문제를 해결할 수 있다.

우선 1일 이용권으로 구매했을 때 가격을 구한다.

그리고 1달 이용권으로 구매했을 때 가격을 구한다.

마지막으로 3달 이용권으로 구매했을 때 가격을 구한다.

처음 결괏값을 1년 이용권으로 할당해 앞선 과정의 결과와 비교해 최종적으로 나온 값을 출력하면 된다.

 

💡 소스코드

---

package SWEA;

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

public class SWEA_P1952_수영장 {
	static int[] fee = new int[4]; 
	static int[] days = new int[13];
	static int result;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("./SWEA_INPUT/SWEA_P1952_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sz;
		int T = Integer.parseInt(br.readLine());

		for (int TC = 1; TC <= T; TC++) {
			sz = new StringTokenizer(br.readLine());
			for (int i = 0; i < 4; i++)
				fee[i] = Integer.parseInt(sz.nextToken());

			sz = new StringTokenizer(br.readLine());
			for (int i = 1; i <= 12; i++)
				days[i] = Integer.parseInt(sz.nextToken());

			result = fee[3];
			DFS(1, 0);
			System.out.println("#" + TC + " " + result);
		}
		br.close();
	}

	public static void DFS(int month, int sum) {
		if (month == 13) {
			result = result > sum ? sum : result;
			return;
		}

		if (days[month] == 0)
			DFS(month + 1, sum);

		if (days[month] > 0)
			DFS(month + 1, sum + days[month] * fee[0]);

		DFS(month + 1, sum + fee[1]);

		if (month <= 10)
			DFS(month + 3, sum + fee[2]);
	}
}

 

💡 결과

---

완전 탐색이 익숙하지 않다면 쉽게 모든 경우의 수를 확인한다고 생각하면 된다.

완전 탐색의 경우는 반복적인 작업이 이루어지는 경우가 많기 때문에 반복적인 작업을 통해 모든 경우의 수를 확인하고

동시에 탈출 조건까지 생각하면 문제를 빠르게 해결할 수 있다.