백준 9327 자바 - 용량 확보 (BOJ 9327 JAVA)

문제 : boj9327

 

 

  음주코딩이 더 코딩이 잘된다는게 사실인것같다. 평소엔 시간 꽤나 걸리던 골1과 플5 문제가 둘다 한방에 해결됬다. 뭐지.. 이상하다. 아무래도 이것저것 복잡도 계산 해볼 정신머리가 없어서 무지성으로 짜보다 보니 오히려 빨리 해결하는 것 같다 ㅋㅋㅋ

 

  결국 입력으로 주어진 n개의 용량x2에 대해 존재 가능한 모든 합의 경우의 수 중, 확보하려는 용량 e보다 같거나 큰 것 중 가장 가까운걸 출력하면 된다.

예를들어 n개가 400 600 700 일 경우 존재 가능한 모든 합의 경우의 수는 다음과 같다.

400

1000

1100

600

1300

700

이걸 정렬하면 400 600 700 1000 1100 1300 이 되고, 이 중 만약 e가 1050이라면 1050보다 같거나 큰 수중 가장 가까운 1100을 출력하면 된다.

 

  따라서 입력받으면서 수가 들어올 때 마다 가능한 경우의 수를 계산해서 다시 추가해주고(단, 중복값은 버림), 정렬 후 순회하면서 e보다 같거나 큰 값을 찾으면 해당 값이 즉시 답이 된다. e보다 같거나 큰 값이 없을 경우 "FULL"을 출력해준다.

 

 

 코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

public class Main extends FastInput {
    private void solution() throws Exception {
        int tc = nextInt();
        StringBuilder sb = new StringBuilder();
        while (tc-->0) {
            int n = nextInt();
            int e = nextInt();
            ArrayList<Integer> list = new ArrayList<>();
            HashSet<Integer> hs = new HashSet<>();
            list.add(0);

            while (n-->0) {
                int cur = nextInt() * 2;
                int size = list.size();
                for (int i = 0; i < size; i++) {
                    int tmp = list.get(i) + cur;
                    if (!hs.contains(tmp)) {
                        hs.add(tmp);
                        list.add(tmp);
                    }
                }
            }

            Collections.sort(list);
            boolean isFull = true;
            for (int i : list) {
                if (i >= e) {
                    sb.append(i/2).append('\n');
                    isFull = false;
                    break;
                }
            }
            if (isFull) {
                sb.append("FULL").append('\n');
            }
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}