[JAVA] SWEA 1486 장훈이의 높은 선반

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

SW Expert Academy

 

1. 서론

 

나는 진짜 SWEA의 등급 매기는 기준을 모르겠다. 이게....D4? D3이면 될 듯.

아주 기초적인 부분집합 문제이다. 백트래킹으로도 풀 수 있다고 한다.

 

2. 문제 풀이

 

배열에 숫자가 주어지고 그 숫자들의 합이 주어진 b보다 크거나 같은 경우 중 가장 작은 수를 구해서 b와의 차를 구하는 문제이다.

배열에 n개의 숫자가 주어진다면 최소 1개, 최대 n개까지의 합을 구해서 b보다 크면서도 합 중에서는 가장 작은 값을 구해 그 값과 b의 차를 구하는 문제이다.

 

위에서도 말했든 1~n개의 부분집합을 만들어서 합을 만들어야 한다. 그 과정을 부분집합 코드를 활용해서 구할 수도 있고, 백트래킹으로 하나씩 더해보고 빼보면서 재귀로 답을 구할 수도 있다.

 

3. 코드 설명

 

1) 부분집합 버전

 

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


public class Solution {
	
	static int ans, n, b;
	static int[] h;
	static boolean[] select;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int t = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for (int q = 1; q <= t; q++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	n = Integer.parseInt(st.nextToken());
        	b = Integer.parseInt(st.nextToken());
        	
        	h = new int[n];
        	st = new StringTokenizer(br.readLine());
        	for (int i = 0; i < n; i++)
        		h[i] = Integer.parseInt(st.nextToken());
        	
        	ans = Integer.MAX_VALUE;
        	select = new boolean[n];
        	subset(0);
        	sb.append("#" + q + " " + (ans - b) + "\n");
        	
        }
        bw.write(sb.toString());
        bw.close(); br.close();
    }
    
    public static void subset(int cnt) {
    	if (cnt == n) {
    		int sum = 0;
    		for (int i = 0; i < n; i++) {
    			if (select[i]) 
    				sum += h[i];
    		}
    		
    		if (sum >= b)
    			ans = Math.min(sum, ans);
    		return;
    	}
    	
    	select[cnt] = true;
    	subset(cnt + 1);
    	select[cnt] = false;
    	subset(cnt + 1);
    }
}

 

뭐 때문인지 또 줄이 안 맞네... 이클립스에서는 맞았는데

하여튼 subset 함수에서 부분집합을 구하고, 다 구해지면 그값을 더해서 b보다 크거나 같은지 체크하고 min 함수를 통해 가장 작은 수를 구한다.

 

 

2) 백트래킹 버전

 

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


public class Solution {
	
	static int ans, n, b;
	static int[] h;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int t = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for (int q = 1; q <= t; q++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	n = Integer.parseInt(st.nextToken());
        	b = Integer.parseInt(st.nextToken());
        	
        	h = new int[n];
        	st = new StringTokenizer(br.readLine());
        	for (int i = 0; i < n; i++)
        		h[i] = Integer.parseInt(st.nextToken());
        	
        	ans = Integer.MAX_VALUE;
        	subset(0, 0);
        	sb.append("#" + q + " " + (ans - b) + "\n");
        	
        }
        bw.write(sb.toString());
        bw.close(); br.close();
    }
    
    public static void subset(int cnt, int sum) {
    	if (sum >= b) {
			ans = Math.min(sum, ans);
			return;
    	}
    	if (cnt == n) return;
    	
    	subset(cnt + 1, sum + h[cnt]);
    	subset(cnt + 1, sum);
    }
}

 

subset함수에서 배열을 한 칸씩 탐색하면서 한번은 그 값을 더하고, 한 번은 더하지 않아서(빼는 역할) 백트래킹을 활용해 합을 만들고 그 합이 b보다 크거나 같은 경우에 최솟값을 구한다. 그리고 공집합 등등의 예외를 처리하기 위해 cnt 가 n인 경우는 함수를 종료한다.

 

백트래킹 버전이 더 간결하고 시간도 적게 걸리지만 난 아직도 재귀 구현이 어려워서 부분집합 버전이 더 편한 건 어쩔 수가 없다.... ㅠ