[SWEA] 1468. 장훈이의 높은 선반

SW Expert Academy

문제

장훈이는 서점을 운영하고 있다. 서점에는 높이가 B인 선반이 하나 있는데 장훈이는 키가 매우 크기 때문에, 선반 위의 물건을 자유롭게 사용할 수 있다.

어느 날 장훈이는 자리를 비웠고, 이 서점에 있는 N명의 점원들이 장훈이가 선반 위에 올려놓은 물건을 사용해야 하는 일이 생겼다. 각 점원의 키는 Hi로 나타나는데, 점원들은 탑을 쌓아서 선반 위의 물건을 사용하기로 하였다.

점원들이 쌓는 탑은 점원 1명 이상으로 이루어져 있다. 탑의 높이는 점원이 1명일 경우 그 점원의 키와 같고, 2명 이상일 경우 탑을 만든 모든 점원의 키의 합과 같다.

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

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, B(1 ≤ N ≤ 20, 1 ≤ B ≤ S)가 공백으로 구분되어 주어진다. S는 두 번째 줄에서 주어지는 점원들 키의 합이다. 두 번째 줄에는 N개의 정수가 공백으로 구분되어 주어지며, 각 정수는 각 점원의 키 Hi(1 ≤ Hi≤10,000)을 나타낸다.

출력

각 테스트 케이스마다 첫 번째 줄에는 ‘#t’(t는 테스트 케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 만들 수 있는 높이가 B 이상인 탑 중에서 탑의 높이와 B의 차이가 가장 작은 것을 출력한다.

구조화

N명에 해당하는 사람들의 키가 주어지고, 그 중 일부 인원의 키의 합이 B보다 크거나 같으면서 최소가 되는 값을 찾는 문제이다. 문제에 맞게 처음에 순열로 인원을 뽑아 값을 도출해 내었는데 8번 테스트 케이스에서부터 시간초과가 발생했다.. 시간을 줄일 수 있는 방법을 찾다가, 순열이 잘못되지 않았을까? 하는 생각에 부분집합으로 해보면 어떨까 싶어서 구현해보았는데 여지없이 정답이 되었다.

• 단순 부분집합 구현

코드

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

public class swea_1468 {
	static int N, B, S, ans;
	static int[] arr, arr2;
	static boolean[] isVisited;
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int t = 1 ; t <= T ; t ++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			ans = Integer.MAX_VALUE;
			arr = new int[N];
			isVisited = new boolean[N];
			
			st = new StringTokenizer(br.readLine());
			for(int i = 0 ; i < N ; i ++)
				arr[i] = Integer.parseInt(st.nextToken());
			subset(0);
			System.out.println("#"+t+" "+ (ans-B));
		}
	}
	
	static void subset(int cnt) {
		if(cnt == N) {
			int sum = 0;
			for(int i = 0 ; i < N ; i ++) {
				if(isVisited[i]) {
					sum += arr[i];
				}
			}
			if(sum >= B && ans > sum)
				ans = sum;
			return;
		}
		
		isVisited[cnt] = true;
		subset(cnt+1);
		isVisited[cnt] = false;
		subset(cnt+1);
	}
}