[ SWEA / 자바 ] 1486번 장훈이의 높은 선반

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

SW Expert Academy

 

---

---

📑 문제

점원의 키를 합쳐서 B 이상의 높이를 만들되, 그 중 가장 낮은 점원 키의 합을 출력하는 문제

 

💡 입력

✔ 맨 첫 줄은 테스트케이스 개수

✔ 점원의 수 N과 높이 B는 (1≤ N ≤ 20, 1 ≤ B ≤ S)

     ✔ S : 두번째 줄에서 주어지는 점원들 키의 합

✔ 각 점원의 키인 N개의 정수는 공백으로 구분되어 주어짐 (1≤H≤20,000)

 

 

---

---

✨ 풀이과정

✔ 비트마스킹을 이용하여 부분집합의 원소들을 구해 키의 합을 만든다

✔ 키의 합이 B보다 큰 경우 (기존의 정답값)과 (이번에 구한 키의합-B)를 비교하여 더 작은 값으로 정답값을 갱신한다

---

---

📑 코드

import java.util.Scanner;
 
public class Solution {
    static int N; //점원의 수
    static int B; //선반의 높이
    static int[] height; //점원 개개인의 키
    static int ans; //가장 작은 차이
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int T = sc.nextInt(); //테스트케이스
         
        for(int tc=1; tc<=T; tc++) {
             
            N = sc.nextInt();
            B = sc.nextInt();
             
            height = new int[N]; //점원들의 키를 담은 배열
             
            for(int i=0; i<N; i++) {
                height[i] = sc.nextInt(); //각각의 키 입력
            }
             
            ans = Integer.MAX_VALUE; //가장 작은 차이를 구해야 하므로 초기값은 MAX_VALUE로 설정
             
            for(int i=1; i<(1<<N); i++) { //공집함을 제외한 N개의 키로 만들 수 있는 부분집합 중
                int result=0; //부분집합이 달라지면 결과 초기화
                for(int j=0; j<N; j++) { 
                    if((i & (1<<j))>0) { //j번째 원소가 부분집합 i에 포함되면
                        result += height[j]; //결과(키의 합)에 더해준다
                    }
                }
                 
                if(result >= B) ans = Math.min(ans, result-B); //B 이상의 합일 경우, 기존보다 B와의 차이가 작은 합인지 비교하고 갱신
                else continue; //결과가 B보다 작으면 다음 부분집합으로 넘어간다
            }
             
            //출력문
						System.out.println("#"+tc+" "+ans);
         
        }//testCase
    } //main
 
 
     
}