[SWEA] 1486. 장훈이의 높은 선반(부분집합/자바)

문제 요약

탑의 높이가 B 이상인 경우 선반 위의 물건을 사용할 수 있는데 탑의 높이가 높을수록 더 위험하므로 높이가 B 이상인 탑 중에서 높이가 가장 낮은 탑을 알아내려고 한다.

 

 

문제 접근 방법

점원들의 키에 대해 일부를 선택하여 선택한 점원들의 키의 합이 B보다 큰 경우 결과 값에 대해 갱신한다.

점원들 중에서 일부를 선택하는 것은 부분 집합으로 구현해볼 수 있다.

현재 점원을 선택한 경우와 선택하지 않는 경우에 대해 재귀 함수를 호출한다. 특히, 현재 점원의 선택 여부를 확인하기 위해서 boolean 배열을 사용하였다. 현재 점원을 선택하면 true, 그렇지 않은 경우는 false로 세팅한다.

재귀 함수의 탈출 조건은 선택한 점원의 수가 N명이 되는 경우이다. 이 경우에 점원들의 키의 합을 구하고, 이 합이 B보다 큰 경우 Math.min을 통해 결과를 갱신한다.

 

 

public class Solution_1486 {
	static boolean[] visited;
	static int N;
	static int B;
	static int result;
	static int[] height;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			result = Integer.MAX_VALUE;
			
			N = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			
			height = new int[N];
			visited = new boolean[N];
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				height[i] = Integer.parseInt(st.nextToken());
			}
			
			solve(0);
			sb.append(String.format("#%d %d\n", tc, Math.abs(result-B)));
		}
		System.out.println(sb);
	}
	
    //부분 집합
	static void solve(int cnt) {
		if(cnt == N) {
			int sum = 0;
			for (int i = 0; i < visited.length; i++) {
				if(visited[i]) {
					sum += height[i];
				}
			}
			if(sum >= B) {//합이 B보다 큰 경우 갱신
				result = Math.min(result, sum);
			}
			return;
		}
		
		visited[cnt] = true;
		solve(cnt+1);
		
		visited[cnt] = false;
		solve(cnt+1);
	}
	
}