SWEA 1486 장훈이의 높은 선반(JAVA) ↑

문제 링크

SW Expert Academy

문제 설명

부분집합 중 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이상인 경우의 수만 골라냄

이 때 그 값과 B의 차이가 가장 적은 경우 출력

소스 코드

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

public class Solution {

	/*
	 * T: 테스트 케이스
	 * N: 직원의 수
	 * B: B이상이여야 함
	 */
     
	static int T, N, B, result;
	static int[] person;
	static boolean[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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());
			
			result = Integer.MAX_VALUE;
			person = new int[N];
			visited = new boolean[N];
			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) 
			{
				person[n] = Integer.parseInt(st.nextToken());
			}
			
			// 부분 집합
			subSet(0);
			System.out.printf("#%d %d%n",t,result);
		}
		
	}
	private static void subSet(int cnt) {

		// 기저 조건
		if(cnt==N)
		{
			int sum = 0;
			for (int i = 0; i < N; i++) {
				if (visited[i]) {
					sum+=person[i];
				}
			}
			if(sum>=B)
			{
				int diff = sum-B;
				result = Math.min(diff, result);
			}
			
			return;
		}
		
		visited[cnt] = true;
		subSet(cnt+1);
		visited[cnt] = false;
		subSet(cnt+1);
	}

}