백준 15810 - 풍선 공장(자바 - 이분탐색)

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

15810번: 풍선 공장

 

* 문제 요약

전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다.

풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는데 걸리는 시간은 다양하다.

대회가 시작되고 운영진으로부터 M개의 풍선을 만들어달라는 의뢰가 들어왔다!

각 스태프가 풍선 하나를 만드는 시간(분) Ai 를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?

풍선을 만든 후에 문제를 표시할 것이기 때문에 풍선의 종류는 상관이 없다.

모든 스태프는 풍선을 만드는데에 정확하게 자신이 말한 시간만큼 걸린다. 예를 들어 스태프 A가 풍선 하나를 만드는데 5분이 걸린다면, 0분에 만들기 시작해서 5분에 끝난다.

 

* 입력

스태프의 수 N과 풍선의 갯수 M이 입력된다. (1 <= N, M <= 1,000,000)

다음 줄에 N명의 각 스태프들이 풍선 하나를 만드는데 걸리는 시간 Ai 가 순서대로 주어진다. Ai는 1,000,000 이하의 자연수이다.

 

* 출력

M개의 풍선이 다 만들어지는 최소 시간을 출력한다.

 

* 예시

 

* 해결 과정

각 스태프들이 풍선을 부는데 걸리는 시간을 ballonTime 배열에 저장해준 다음, 이 배열을 오름차순 정렬한다.

start 를 0, end 를 오름차순 정렬된 배열의 가장 앞에 있는 요소. 즉, 풍선을 가장 빨리 부는 스태프를 기준으로 이 스태프가 모든 풍선을 부는 경우를 가정한 값 (ballonTime[0] * M) 으로 초기화해준다.

(물론 풍선을 가장 빠르게 부는 경우는 모든 스태프들이 자신의 몫만큼 풍선을 불다가, 풍선을 빨리 부는사람 순서대로 아직 풍선을 다 못 분 사람 것을 불어주는 것이겠지만, 여기서 end 의 경우 상정할 수 있는 경우 중 풍선을 부는 시간이 오래 걸리는 경우로 잡아놓아야 한다. 당연히 가장 오래 걸리는 경우는 풍선을 가장 느리게 부는 사람이 모든 풍선을 부는 것이겠지만 범위가 그렇게 되면 괜히 이분탐색을 하는데 필요한 반복횟수만 더 늘어나기에 이분탐색을 위해 반복을 수행하는 횟수를 조금이라도 더 줄이기 위해 풍선을 가장 빨리 부는 사람을 기준으로 그 사람이 모든 풍선을 부는 경우를 end 로 설정해주었다.)

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

  - mid 를 (start + end) / 2 로 초기화해준다. 여기서 mid는 M개의 풍선을 모두 부는데 걸리는 시간에 해당한다.

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

    - standardTime을 mid 값으로 초기화해준다.

    - 반복문을 통해 주어진 standardTime 시간동안 각 스태프가 풍선을 몇 개씩 불 수 있는지 계산해서 sum 변수에 합산해준다. (sum += standardTime / (long)ballonTime[i];)

    - 반복문을 수행해서 얻은 sum 값이 M보다 작다면 주어진 시간동안 M개의 풍선을 불지 못한다는 뜻이므로 false 를 반환해준다.

    - 그렇지 않은 경우 M개의 풍선을 주어진 시간동안 불 수 있다는 뜻이므로 true 를 반환해준다.

  - check(long mid) 메소드 실행 결과 true 를 반환받았다면 end 를 mid - 1 로 초기화하여 mid 값이 더 작아지는 방향으로(주어지는 시간이 더 작아지는 방향으로) 범위를 줄여준다.

  - check(long mid) 메소드 실행 결과 false 를 반환받았다면 주어진 시간이 부족했다는 뜻이므로 start 를 mid + 1 로 초기화하여 mid 값이 더 커지는 방향으로 범위를 줄여준다.

2. 반복문이 끝나고 나면 start 를 출력시켜준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    static int N = 0;
    static int M = 0;
    static int[] ballonTime = null;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] inputArray = br.readLine().split(" ");
        N = Integer.parseInt(inputArray[0]);
        M = Integer.parseInt(inputArray[1]);

        ballonTime = new int[N];
        inputArray = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            ballonTime[i] = Integer.parseInt(inputArray[i]);
        }

        Arrays.sort(ballonTime);
        long start = 0;
        long end = (long) ballonTime[0] * (long) M;

        while (start <= end) {
            long mid = (start + end) / 2;

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

        bw.write(start + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean check(long mid) {

        boolean result = true;
        long standardTime = mid;

        long sum = 0;
        for (int i = 0; i < ballonTime.length; i++) {
            sum += standardTime / (long) ballonTime[i];
        }

        if (sum < M) {
            result = false;
        }
        return result;
    }
}

 

M개의 풍선을 부는데 걸릴 최소, 최대 시간을 범위로 잡고 각 범위의 중간값을 기준으로 시간이 주어질 때 M개 만큼의 풍선을 모두 불 수 있는지 없는지에 따라 범위를 줄여가며 M개의 풍선을 부는데 필요한 최소 시간을 찾았으므로 매개변수 탐색 문제에 해당된다.