SWEA : 수영장 문제 [자바][2021.10 기록]

참고한 블로그 : https://hoho325.tistory.com/112

[SWEA] 모의 SW 역량 테스트 :: 1952번 수영장 자바(java) 풀이

[ 깔끔한 코드 + 설명에 문제를 이해하는데 도움이 되었다. ]

 

---

정답률 66%대 문제.

 

문제를 봤을 때는 그리디하게 접근해야 하는 줄 알았다.

 

이성적으로 3달 요금이 1달 요금보다 저렴할 것이기 때문이다.

 

하지만 문제에는 이성적으로 3달 요금이 3달치 비용보다 저렴할 것이라는 얘기가 나오지 않았다.

 

3달 요금이 1달 요금보다 저렴할 수도 있다는 얘기이다.

 

실제로 다음의 테스트 케이스를 보면 3달치 요금이 1달치 요금보다 훨씬 저렴하다는 것을 알 수 있다.

[ 그 외의 테스트 케이스에서는 3달치 요즘이 실제 1달 x 3을 낸 비용보다는 저렴했다. ]

10 100 50 300
0 0 0 0 0 0 0 0 6 2 7 8

 

그리디한 접근법으로 3달치 비용이 효율적인 위치를 기억하는 방식으로 접근했는데 여기서 화를 입은 것이다.

 

다른 히든 케이스까지 고려한다면 해당 문제는 완전 탐색으로 접근하는 것이 안전하다. 

 

[ 다른 방식으로는 동적 프로그래밍(메모이제이션) 방식도 존재한다. ] [ 개인적으로 DP가 깔끔해 보인다. ]

 

하나의 테스트 케이스를 정말 탐색해서 얻은 최소의 요금과 1년치 요금을 비교해서 1년 치가 저렴하면 1년 치를, 최소 요금이 더 저렴하면 최소 요금을 반환하면 된다.

 

핵심이 되는 완전 탐색 파트

	static void dfs(int cnt, int sum) {
		if(cnt >= 12) {
			min = Math.min(sum, min);
			return ;
		}
		// 이용일 수 0인 달은 비용을 더하지 않는다.
		if(uses[cnt] == 0) {
			dfs(cnt + 1, sum);
		} else {
			System.out.println("day start d " + ++depth);
			dfs(cnt + 1, sum + (uses[cnt] * fees[0])); // 하루 이용권 사용한 경우
			System.out.println("month start d " + ++depth);
			dfs(cnt + 1, sum + fees[1]); // 한 달 이용권 사용한 경우
			System.out.println("3month start " + ++depth);
			dfs(cnt + 3, sum + fees[2]); // 세달 이용권 사용한 경우
			System.out.println("last " + ++depth);
		}
	}

깊이 우선 탐색 방식으로 완전 탐색을 진행했다.

 

3가지의 방식에 대한 깊이 우선 탐색을 진행한다. [ 1일권, 1달권, 3달권 ]

3달권의 경우 이후의 3달치 요금이 필요가 없기에 idx에 + 3으로 넘긴다.

 

위의 식으로 풀게 되면

 

하루 -> 하루 -> 하루 -> 하루

 

하루 -> 하루 -> 하루 -> 달

 

하루 -> 하루 -> 하루 -> 3달

 

이런 식으로 모든 방식으로 탐색하게 된다. 그리고 최종 조건(cnt가 12인 경우)에 값을 비교해서 최솟값으로 지정하면 된다.

 

전체 코드

 

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

public class Solution {

	// 1일, 1달, 3달, 1년 | 매달 1일부터 시작(달 이용권들은)
	// 가장 적은 비용
	static int T;
	static int[] fees;
	static int[] uses;
	static boolean[] checks;
	static boolean yearCheck;
	static String[] strs = null;
	static int min;
	static int depth = 0;
	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < T; i++) {
			strs = br.readLine().split(" ");
			fees = new int[4];
			for(int idx = 0; idx < 4; idx++) fees[idx] = Integer.parseInt(strs[idx]);
			
			
			uses = new int[12];
			strs = br.readLine().split(" ");
			for(int p_idx = 0; p_idx < 12; p_idx++) uses[p_idx] = Integer.parseInt(strs[p_idx]);
			
			min = Integer.MAX_VALUE;
			dfs(0, 0);
			min = Math.min(fees[3], min); // 1년 이용권 사용금액과 비교하기
			System.out.println("#" + (i+1) + " " + min);
		}
	}
	
	static void dfs(int cnt, int sum) {
		if(cnt >= 12) {
			min = Math.min(sum, min);
			return ;
		}
		// 이용일 수 0인 달은 비용을 더하지 않는다.
		if(uses[cnt] == 0) {
			dfs(cnt + 1, sum);
		} else {
			System.out.println("day start d " + ++depth);
			dfs(cnt + 1, sum + (uses[cnt] * fees[0])); // 하루 이용권 사용한 경우
			System.out.println("month start d " + ++depth);
			dfs(cnt + 1, sum + fees[1]); // 한 달 이용권 사용한 경우
			System.out.println("3month start " + ++depth);
			dfs(cnt + 3, sum + fees[2]); // 세달 이용권 사용한 경우
			System.out.println("last " + ++depth);
		}
	}
}

 

후기. 완전 탐색은 이해했다가도 막상 문제에 적용할려고 하면 머리가 하얘진다.

 

순열, 조합, 그래프 탐색, 완전탐색 등등에 활용되는 완전탐색 방식.

 

최솟값 혹은 최댓값을 찾으라는 문제에는 DP와 DFS, BFS부터 빠르게 고민해야 한다.

 

순열과 조합에 대한 조건 체크도 마찬가지이다.

 

계속 연습해서 문제를 풀어가야겠다.

 

삼성 SW 역량 테스트는 시뮬레이션 + DFS, BFS, DP가 주 문제라고 한다.

 

해당 유형은 다른 코테에서도 자주 보이는 유형이기에 SWEA의 모의 역량테스트를 푸는 것도 좋아 보인다.

 

완전탐색 + DP는 계속 경험해보는게 제일 좋은 것 같다.