[SWEA] 1486. 장훈이의 높은 선반 - Java

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

SW Expert Academy

---

1. 문제 요약

점원 N명이 탑을 쌓아서 높이가 B 이상일 때 최소가 되는 높이를 구하려고 한다.

 

2. 풀이

부분집합 문제이다.

2가지 방법으로 풀었다.

첫 번째는

부분집합으로 N번 다 봤을 때 기저조건에서 check() 함수로

for문으로 선택한 녀석들을 하나하나 찾아 합을 구해줬다. 그리고 B 이상일 경우 최솟값을 갱신해줬다.

근데 이렇게 하면 불필요한 반복이 일어난다.

그래서 수정한 두 번째 방법은

선택한 녀석들만의 합을 파라미터로 보내서 부분집합 함수 호출할 때마다 최솟값을 갱신을 해주는 것이다.

첫 번째

두 번째

두 번째가 더 빠르다.

 

3. 코드

첫 번재 방법

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

public class Solution {

	static int N, B, ans;
	static int[] height;
	static boolean[] isSelected;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			
			height = new int[N];
			isSelected = new boolean[N];
			
			st = new StringTokenizer(br.readLine());
			for (int i=0; i<N; i++) {
				height[i] = Integer.parseInt(st.nextToken());
			} //입력 끝
			
			ans = Integer.MAX_VALUE;
			subset(0);
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void subset(int cnt) {
		if (cnt == N) {
			check();
			return;
		}
		
		isSelected[cnt] = true;
		subset(cnt+1);
		isSelected[cnt] = false;
		subset(cnt+1);
	}
	
	static void check() {
		int sum = 0;
		for (int i=0; i<N; i++) {
			if (isSelected[i] == true) {
				sum += height[i];
			}
		}
		if (sum >= B) {
			ans = Math.min(ans, sum-B);
		}
	}
}

두 번째 방법

package a22_11_12;

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

public class SW_1486_장훈이의높은선반 {

	static int N, B, ans;
	static int[] height;
	static boolean[] isSelected;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			
			height = new int[N];
			isSelected = new boolean[N];
			
			st = new StringTokenizer(br.readLine());
			for (int i=0; i<N; i++) {
				height[i] = Integer.parseInt(st.nextToken());
			} //입력 끝
			
			ans = Integer.MAX_VALUE;
			subset(0, 0);
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void subset(int cnt, int sum) {
		if (sum>=B) ans = Math.min(ans, sum-B);
			
		if (cnt == N) {
			return;
		}
		
		isSelected[cnt] = true;
		subset(cnt+1, sum + height[cnt]);
		isSelected[cnt] = false;
		subset(cnt+1, sum);
	}
}

 

4. 사담

부분집합의 정석 문제인 것 같다

시험에 이런 문제만 나왔으면 얼마나 좋을까