백준 18113 - 그르다 김가놈 (자바 - 이분탐색)

https://www.acmicpc.net/problem/18113

18113번: 그르다 김가놈

 

* 문제 요약

정래는 김밥 가게 "그르다 김가놈" 에 납품할 김밥을 만드는 김밥 공장을 운영한다. 정래는 김밥 양쪽 끝을 "꼬다리" 라고 부른다. 그리고 꼬다리를 잘라낸 김밥을 "손질된 김밥" 이라고 부른다. 

공장에서는 김밥 N개에 대해서, 김밥 꼬다리를 잘라내고 손질된 김밥을 김밥 조각으로 만드는 작업을 한다.

꼬다리를 잘라낼 때에는 양쪽에서 균일하게 K cm 만큼 잘라낸다. 만약 김밥의 길이가 2K 보다 짧아서 한쪽 밖에 자르지 못한다면 한쪽만 꼬다리를 잘라낸다.

김밥 길이가 K cm 이거나 그보다 짧으면 그 김밥은 폐기한다.

손질된 김밥은 모두 일정한 길이 P로 잘라서 P cm 김밥 조각들로 만든다. P는 양의 정수여야 한다.

정래는 일정한 길이 P cm 로 자른 김밥 조각을 최소 M개 만들고 싶다. P를 최대한 길게 하고 싶을 때, P는 얼마로 설정해야 하는지 구하시오.

 

* 입력

첫 번째 줄에 손질해야 하는 김밥의 갯수 N, 꼬다리의 길이 K, 김밥 조각의 최소 갯수 M이 주어진다. (1 <= N <= 10^6, 1 <= K, M <= 10^9, N, K, M은 정수)

 

* 출력

김밥 조각의 길이 P를 최대로 할 때, P를 출력한다. 만족하는 P가 없는 경우 -1을 출력한다.

 

* 예시

 

* 해결 과정

입력받은 김밥들 전체를 대상으로 김밥 조각을 P cm 로 자를 때 만들어질 수 있는 김밥 조각이 M개보다 크거나 같은지, 또는 작은지에 따라 이분탐색을 수행한다.

우선 입력받은 김밥들에 대해 꼬다리 2K cm 만큼 자를 수 있는지 확인하고, 그렇지 않은 경우 K만큼 자를 수 있는지 확인하며, 그조차 안되는 경우 그 김밥은 폐기한다.

중간에 폐기해야 하는 김밥이 나올 수 있으므로 일단은 처음 김밥을 입력받을 때 정상적으로 손질이 가능한 경우 큐에 저장해주고, 그렇지 않은 경우 건너뛰는 식으로 저장해준 다음

손질을 성공한 김밥의 갯수가 나오면 그 크기에 맞춰 배열을 만들고 해당 배열에 각 김밥들의 길이를 저장해준다.

 

손질이 가능한 김밥의 갯수를 따로 저장해주고 나면 잘라낼 김밥 조각의 길이 P의 범위로 start = 0, end 는 손질된 김밥들 중 최대길이로 설정해준 다음, 다음과 같이 이분탐색을 수행해준다.

1. start <= end 조건을 만족하는 동안 다음과 같이 반복문을 수행한다.

  - mid 를 (start + end) / 2 로 초기화해준다. 이때 mid 는 김밥 조각으로 잘라낼 길이 P에 해당된다.

  - kimbapSlice(long mid) 메소드를 실행한다.

    - 손질된 김밥의 각 길이를 기준으로 mid 만큼 나누었을 때 결과값을 sum 변수에 합산한다.

    - 만약 sum 값이 M보다 크거나 같은 경우 true 를 반환해준다. 이 경우 김밥 조각을 M개 이상으로 자를 수 있는 P가 존재한다는 뜻이므로 check 변수를 true 로 변환해준다.

    - 만약 sum 값이 M보다 작은 경우 false 를 반환해준다.

  - kimbapSlice(long mid) 메소드 실행 결과 true 를 반환받은 경우 result 변수를 mid 값으로 초기화해준 다음 start 를 mid + 1 로 초기화하여 mid 값이 더 커지는 방향으로 범위를 줄여준다.

  - 반대로 false 를 반환받은 경우 end 를 mid - 1 로 초기화하여 mid 값이 더 작아지는 방향으로 범위를 줄여준다.

2. 반복문 실행결과 check 변수가 true 인 경우 김밥 조각을 M개 만큼 자를 수 있는 P가 존재하였다는 뜻이므로 result 값을 출력시켜준다.

3. 반대로 check 변수가 false 인 경우 김밥 조각을 M개 만큼 자를 수 있는 P가 존재하지 않는다는 뜻이므로 -1 을 출력시켜준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

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

    static int[] kimbapArray = null;
    static int m = 0;
    static boolean check = false;

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        m = Integer.parseInt(input[2]);

        Queue<Integer> queue = new LinkedList<>();
        // 꼬다리 손질
        for (int i = 0; i < n; i++) {
            int kimbap = Integer.parseInt(br.readLine());

            if (kimbap >= k * 2) {
                if (kimbap - (k * 2) > 0) {
                    queue.offer(kimbap - (k * 2));
                }
            } else if (kimbap > k) {
                queue.offer(kimbap - k);
            }
        }

        if (queue.size() > 0) {
            kimbapArray = new int[queue.size()];
            long max = Integer.MIN_VALUE;
            for (int i = 0; i < kimbapArray.length; i++) {
                kimbapArray[i] = queue.poll();
                max = Math.max(max, kimbapArray[i]);
            }

            long start = 1;
            long end = max;
            long result = 0;
            while (start <= end) {
                long mid = (start + end) / 2;

                if (kimbapSlice(mid)) {
                    result = mid;
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }

            if (check) {
                bw.write(result + "\n");
            } else {
                bw.write(-1 + "\n");
            }
        } else {
            bw.write(-1 + "\n");
            bw.flush();
            bw.close();
            br.close();
            return;
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private boolean kimbapSlice(long mid) {

        long sum = 0;
        for (int i = 0; i < kimbapArray.length; i++) {
            if (kimbapArray[i] >= mid && kimbapArray[i] > 0) {
                sum += kimbapArray[i] / mid;
            }
        }

        if (sum >= m) {
            check = true;
            return true;
        } else {
            return false;
        }
    }
}

 

김밥 조각을 잘라낼 P의 최소, 최대 범위안에서 중간값을 기준으로 김밥을 잘랐을 때 김밥 조각이 M개 이상 나오는지 아닌지에 따라 범위를 줄여가며 P의 최대값을 찾았으므로 매개변수 탐색문제에 해당된다.