SWEA D4 1486 장훈이의 높은 선반

SWEA D4 1486 장훈이의 높은 선반

 

 

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/cxEbPR--nws

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.d4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

/**
 * @author itsmeyjc
 * @since 2019. 1. 23.
 * @see https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE
 * @mem 23,860
 * @time 115 ms
 * @caution #combination, #powerset
 * 몇명이 될 지도, 누가 되는게 좋을지도 알 수 없다 - 전부 다 해보는 경우
 * 조합적으로, 부분집합으로 처리할 수 있는데 조합으로 할 때가(115ms) 부분집합(204ms) 때보다 빠르다.
 */
public class SWEA_D4_1486_장훈이의높은선반 {
    static StringBuilder sb = new StringBuilder();

    static int N;
    static int H;
    
    static int[] clerks;
    static int MinGap; // 최소 차이

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

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

        for (int t = 1; t <= tc; t++) {
            MinGap = Integer.MAX_VALUE;

            StringTokenizer tokens = new StringTokenizer(br.readLine());
            N = Integer.parseInt(tokens.nextToken());
            H = Integer.parseInt(tokens.nextToken());
            clerks = new int[N];
            tokens = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                clerks[i] = Integer.parseInt(tokens.nextToken());
            }

            // makePowerSet();
            combination(0, 0);

            sb.append("#").append(t).append(" ").append(MinGap).append("\n");
        }
        System.out.println(sb);
    }

    static void makePowerSet() {
        for (int i = 1; i < (1 << N); i++) {
            int sum = 0;
            for (int j = 0; j < N; j++) {
                if ((i & (1 << j)) > 0) {
                    sum += clerks[j];
                    if (sum - H > MinGap) {
                        break;
                    }
                }
            }
            if (sum >= H && sum - H < MinGap) {
                MinGap = sum - H;
            }
        }
    }

    static void combination(int start, int sum) {
        if (sum >= H && sum - H < MinGap) {
            MinGap = sum - H;
            return;
        }
        if (start == N) {
            return;
        }

        for (int i = start; i < N; i++) {
            combination(i + 1, sum + clerks[i]);
        }
    }

    // END:

    static String src = "10\n" +
                        "5 16\n" +
                        "3 1 3 5 6\n" +
                        "2 10\n" +
                        "7 7\n" +
                        "3 120\n" +
                        "83 64 36\n" +
                        "4 416\n" +
                        "299 239 116 128\n" +
                        "5 1535\n" +
                        "351 228 300 623 954\n" +
                        "10 2780\n" +
                        "268 61 201 535 464 168 491 275 578 153\n" +
                        "10 1162\n" +
                        "73 857 502 826 923 653 168 396 353 874\n" +
                        "15 8855\n" +
                        "3711 576 9081 3280 1413 6818 5142 2981 1266 484 5757 2451 6961 4862 2086\n" +
                        "15 57209\n" +
                        "8903 5737 3749 8960 724 6295 1240 4325 8023 3640 2223 639 4161 5330 4260\n" +
                        "20 78988\n" +
                        "3811 2307 3935 5052 4936 3473 6432 7032 1560 1992 5332 7000 4020 9344 2732 8815 9924 8998 9540 4640\n" +
                        "";
}