백준 14627 - 파닭파닭 (자바 - 이분탐색)

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

14627번: 파닭파닭

 

* 문제 요약

평소 요리에 관심이 많은 승균이는 치킨집을 개업하였다. 승균이네 치킨집은 파닭이 주메뉴다. 승균이는 가게를 오픈하기 전에 남부시장에 들러서 길이가 일정하지 않은 파를 여러개 구매하였다.

승균이는 파닭의 일정한 맛을 유지하기 위해 각각의 파닭에 같은 양의 파를 넣는다.

또 파닭 맛은 파의 양에 따라 좌우된다고 생각하기 때문에 될 수 있는 한 파의 양을 최대한 많이 넣으려고 한다.

(하지만 하나의 파닭에는 하나 이상의 파가 들어가면 안된다.) 힘든 하루를 마치고 승균이는 파닭을 만들고 남은 파를 라면에 넣어 먹으려고 한다.

이때 라면에 넣을 파의 양을 구하는 프로그램을 작성하시오. 승균이네 치킨집 자는 정수만 표현되기 때문에 정수의 크기로만 자를 수 있다.

 

* 입력

첫째 줄에 승균이가 시장에서 사 온 파의 갯수 S(1 <= S <= 1,000,000), 그리고 주문받은 파닭의 수 C(1 <= C <= 1,000,000) 가 입력된다. 파의 갯수는 항상 파닭의 수를 넘지 않는다. (S <= C)

그 후, S줄에 걸쳐 파의 길이 L (1 <= L <= 1,000,000,000) 이 정수로 입력된다.

 

* 출력

승균이가 라면에 넣을 파의 양을 출력한다.

 

* 예시

 

* 해결 과정

파닭에 들어갈만큼의 파를 모두 쓰고 난 후 남은 파의 길이를 구해줘야 하기 때문에 우선 파의 길이가 입력될때마다 이 값을 sum 변수에 합산해서 입력받은 파의 길이의 총합을 구해준다.

파를 자를 수 있는 최소 길이 1을 start, 입력받은 파들 중 길이가 가장 긴 파의 길이를 end 로 설정해서 범위를 설정해준 다음 다음과 같이 이분탐색을 수행한다.

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

  - mid 를 (start + end) / 2 로 초기화해준다. 이때 mid 는 각 파에서 잘라낼 만큼의 길이를 의미한다.

  - mid 값을 통해 onionSlice(int mid) 메소드를 수행해준다.

    - 입력받은 파들의 길이에 대해 mid 값 만큼 나눠준 값을 count 변수에 합산해준다.

    - 만약 count 가 주문받은 치킨의 갯수보다 크거나 같으면 true 를 반환해준다.

    - 만약 count 가 주문받은 치킨의 갯수보다 작다면 false 를 반환해준다.

  - onionSlice(int mid) 메소드에서 true 를 반환받았을 경우 mid 값으로 파들을 잘랐을 때 주문받은 양 만큼 치킨을 만들어 줄 수 있다는 뜻이므로 greenOnion 변수에 현재 mid 값을 저장해주고 난 다음, start 를 mid + 1 로 초기화해서 mid 값이 더 커지는 방향으로 범위를 줄여준다.

  - onionSlice(int mid) 메소드에서 false 를 반환받았을 경우 end 를 mid - 1 로 초기화해서 mid 값이 더 작아지는 방향으로 범위를 줄여준다.

2. 반복문이 끝나고 나면 파의 길이의 총합(sum) 에서 공통적으로 잘라낼 파의 길이(greenOnion) 와 주문받은 치킨의 갯수(chickenCount) 를 곱한 값을 빼서 result 변수에 저장해주고 난 후 result 를 출력시켜준다.

 

* 코드

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

public class Main {

    static long[] onionArray;
    static int onionCount;
    static int chickenCount;

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

    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(" ");

        onionCount = Integer.parseInt(input[0]);
        chickenCount = Integer.parseInt(input[1]);
        onionArray = new long[onionCount];

        long sum = 0;
        long max = Long.MIN_VALUE;
        for (int i = 0; i < onionCount; i++) {
            onionArray[i] = Long.parseLong(br.readLine());
            sum += onionArray[i];
            max = Math.max(max, onionArray[i]);
        }

        long start = 1; 
        long end = max; 
        long greenOnion = 0;
        while (start <= end) {

            long mid = (start + end) / 2;
            if (onionSlice(mid)) {
                greenOnion = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        long result = sum - (greenOnion * chickenCount);

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

    private boolean onionSlice(long mid) {

        long count = 0;
        for (int i = 0; i < onionArray.length; i++) {
            long onionLength = onionArray[i];
            count += (onionLength / mid);
        }
        if (count >= chickenCount)
            return true;
        else 
            return false;
    }
}

 

자를 수 있는 파의 최소 길이 1부터 입력받은 파들 중 가장 길이가 긴 파의 길이까지를 초기 범위로 설정해준 다음, 해당 범위에서의 중간값으로 각 파들을 자른다고 했을 때 주문받은 양 만큼 치킨을 만들어 줄 수 있는지 없는지에 따라 범위를 줄여가며 치킨에 공통적으로 넣을 수 있는 파의 길이 중 최대값을 구해준 다음 해당 값에 주문받은 치킨의 양을 곱해서 입력받은 파의 전체 길이에서 빼 줌으로서 최종적으로 라면에 넣을 수 있는 파의 길이를 구해주었으므로 매개변수 탐색 문제에 해당된다.