[SWEA][Java] 수영장

문제링크

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

SW Expert Academy

 

# 문제풀이

구현 + DFS

수영장 이용권 중 1일권, 1달권, 3달권, 1년권을 이용하여 1년 이용 비용을 제일 저렴하게 구하는 문제였습니다.

1일권, 1달권, 3달권을 이용하여 구한 값보다 1년권의 가격이 더 저렴하다면 1년권을 결제하고

1일권과 이용날짜를 곱하여 나온 가격과 1달 이용권의 가격 중 더 저렴한 가격으로 계산하여 다음달로 넘기고

매달 3달권을 시작하는 할 수 있는 것까지 계산하여 3달 이후의 달로 넘기는 경우도 추가해서 계산했습니다.

1. 이용권의 가격과 이용계획을 배열로 받습니다.

2. dfs로 탐색합니다. 파라미터로 현재의 달, 현재 달까지 계산한 최소비용을 넣습니다.

- 탐색을 12월달까지 다 했을 경우, 계산한 최소비용과 원래의 최소비용을 비교하여 더 작은 쪽을 저장하고 리턴합니다.

- 3달 이용권을 11월이나 12월에 결제했을 때, 13월보다 더 큰 달을 계산할 수 있다는 것을 고려하여 12보다 클때로 조건을 설정합니다.

- 1일권 비용* 이용날짜가 1달권 비용보다 더 크다면 1달권 비용을 최소 비용을 계산할 때로 포함하고, 그 반대의 경우는 1일권 비용* 이용날짜를 최소 비용을 계산할 때 포함합니다.

- 3달 이용권을 사용했을 경우 더 저렴할 수 있기 때문에, 이 경우에도 dfs를 돌려줍니다.

- 최종으로 12월까지 계산한 값보다 1년 이용권이 저렴하다면 1년 이용권을 최소비용에 저장합니다.

 

# 문제 코드

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

public class SWEA수영장 {
	static int t, minPrice;
	static int[] plist, mlist;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		t = Integer.parseInt(br.readLine());
		for (int tc = 1; tc < t + 1; tc++) {
			plist = new int[4];
			mlist = new int[13];
			minPrice = Integer.MAX_VALUE;

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < plist.length; i++) {
				plist[i] = Integer.parseInt(st.nextToken());
			}

			st = new StringTokenizer(br.readLine());
			for (int i = 1; i < mlist.length; i++) {
				mlist[i] = Integer.parseInt(st.nextToken());
			}

			dfs(1, 0);
			
			if(minPrice > plist[3]) {
				minPrice = plist[3];
			}
			sb.append("#" + tc + " " + minPrice + "\n");
		}
		
		System.out.println(sb.toString());
	}

	public static void dfs(int cMonth, int cPrice) {
		if (cMonth > 12) {
			if (minPrice > cPrice) {
				minPrice = cPrice;
			}
			return;
		}

		if (plist[0] * mlist[cMonth] > plist[1]) {
			dfs(cMonth + 1, cPrice + plist[1]);
		} else {
			dfs(cMonth + 1, cPrice + plist[0] * mlist[cMonth]);
		}
		
		dfs(cMonth + 3, cPrice + plist[2]);
	}
}