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

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

제출일 : 2019-08-22

문제 풀이 시간 : 2H 30M

난이도 : ★★★

Problem

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

Input

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

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, B(1 ≤ N ≤ 20, 1 ≤ B ≤ S)가 공백으로 구분되어 주어진다.

S는 두 번째 줄에서 주어지는 점원들 키의 합이다.

두 번째 줄에는 N개의 정수가 공백으로 구분되어 주어지며, 각 정수는 각 점원의 키 Hi (1 ≤ Hi ≤ 10,000)을 나타낸다.

Output

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

Example

input

1
5 16
1 3 3 5 6

output

#1 1

Solution & Inpression

DFS로도 해결 할 수 있었지만 PowerSet(멱집합)을 이용하여 해결 하였다.

Code

언어 : JAVA

메모리 : 19,768 kb

실행시간 : 182 ms

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

public class Solution{
    public static int N, B, result;
    public static int[] high;

    public static void sol() {
        int i, j;
        for (i = 0; i < (1 << N); ++i) {
            int sum = 0;
            for (j = N - 1; j >= 0; --j) {
                // System.out.print(((i >> j) & 1));
                if (((i >> j) & 1) == 1)
                    sum += high[j];
            }
            // System.out.println();
            if (sum >= B)
                result = (result > sum) ? sum : result;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // N, B(1 ≤ N ≤ 20, 1 ≤ B ≤ S)
            N = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());

            high = new int[N];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++)
                high[i] = Integer.parseInt(st.nextToken());

            result = Integer.MAX_VALUE;
            sol();

            System.out.println("#" + tc + " " + (result - B));
        }
        br.close();
    }
}