1952번 - 수영장

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

 

1일권 / 1달권 / 3달권 / 1년권 이용 요금과

수영장을 각 달마다 몇 번이나 갈지 그 계획이 주어졌을 때

가장 적은 비용으로 수영장을 이용할 수 있는 방법과 그 비용을 구하는 문제이다.

나는 완전 탐색을 이용해서 풀었다.

 

 

1일권만 사용했을 때, 1달권만 사용했을 때 예상 금액

 

우선 나는 인덱스의 크기를 +1 만큼 잡아줬다.

0부터 시작하면 헷갈리니까!

 

표를 보면 1일권만 사용했을 때 드는 비용과 1달권만 사용했을 때 드는 비용을 확인할 수 있다. 

우리는 표를 통해 1달권 요금 < 이용 일수 * 1일권 요금이면 1달권을 사용하는 게 유리하는 것을 알 수 있다.

계산을 통해 몇 일 이상이면 1달권을 구매하는 게 유리하구나! 를 알아내서 비교해도 좋다. 그게 그거니까

 

 

1일권, 1달권 조합으로 가장 최선의 조합을 짜는 경우

 

그렇게 각 달마다 1일권/1달권 중 저렴한 방법으로 계산해서 요금을 측정했다.

 

이제 3달권 이용금액과 앞에서 구한 이용금액 중 무엇을 구매하는 게 이득일지를 비교해봐야 한다.

모든 경우를 따지기 위해서 우린 결국 완전탐색을 사용해야 한다.

단, 연간권은 탐색하면서 비교할 필요 없이 탐색한 결과와 딱 한 번만 비교하면 된다.

 

다시 잘 정리해서 말해보자면

1. 1일권과 1달권 중 유리한 이용권을 고른다.

2. 1번에서 구한 월별 금액과 3달권 중 유리한 이용권을 고른다.

3. 2번에서 구한 금액과 연간권 중 유리한 이용권을 고른다.

끝!

 

 

2. 코드

package algorithm;

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

public class Day15_수영장 {
	static int[] prices; // 티켓 가격
	static int[] plans; // 수영장을 몇번 이용할건지 계획
	static int[] min; // 월별 최소 예상금액
	static final int TYPECNT = 4; // 티켓의 종류
	static final int MONCNT = 12; // 12개월
	static int bestPrice;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int testCase = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= testCase; tc++) {
			prices = new int[TYPECNT];
			plans = new int[MONCNT + 1];
			min = new int[MONCNT + 1];

			// 이용권 금액
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < TYPECNT; i++) {
				prices[i] = Integer.parseInt(st.nextToken());
			}

			// 이용 계획
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= MONCNT; i++) {
				plans[i] = Integer.parseInt(st.nextToken());
			}

			// 1일권과 1달권 중 이득인 것 선택하기
			for (int i = 1; i <= MONCNT; i++) {
				min[i] = Math.min(prices[1], prices[0] * plans[i]);
			}

			bestPrice = prices[3];
			dfs(1, 0);
			sb.append("#").append(tc).append(" ").append(bestPrice).append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	public static void dfs(int idx, int sum) {
		// 탐색이 끝났다면
		if (idx == 13) {
			// 최소 비용 업데이트
			if (sum < bestPrice) {
				bestPrice = sum;
				return;
			}
		}

		// 가지치기
		if (sum >= bestPrice) {
			return;
		}

		if(idx <= 10) dfs(idx + 3, sum + prices[2]); // 3달 이용권으로 결제해버려~
		dfs(idx + 1, sum + min[idx]); // 한 달은 그냥 긁고 다음 3개월치 조사해보자.
	}
}

이용권 합계를 구하다가 이전에 구한 금액을 넘어서면 더 이상을 탐색하지 않도록 가지치기를 넣어놨다.

 

 

3. 실행시간

 

 

 

 

---

💡 느낀 점

• 반년전에 날 코딩 테스트에서 떨어트린 문제와 비슷해서 흠칫
• 그때는 알고리즘의 '알'도 모를 때라 하나도 못 풀었었는데.. 그래도 발전하긴 했나 보다.
• 코드를 깔끔하게 하고 싶다면 dfs에서 1일권과 한 달권을 비교하는 게 나을 것 같다.
• 속도를 빠르게 하고 싶다면 1일권 한달권을 비교 후 dfs로 들어가는 게 빠를 듯

---