[JAVA] 백준 과자 나눠주기

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

 

이분탐색 문제였다.

처음에는 Priority Queue로 각각의 경우를 나눠주는 방식으로 접근했지만, 아래 예시와 같은 경우를 따지려니 실패하였다.

 

ex) 3명의 조카에게 1개의 과자 3cm인 경우=> 3등분 해야함.

 

따라서 위 방식은 잘못되었음을 깨닫고 이분탐색 방식으로 진행해야했다.

 

 

import java.io.*;
import java.util.*;

public class Main {
    static int[] arr;
    static int m, n,result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        binarySearch(1, arr[n-1]);

        System.out.println(result);
    }

    public static void binarySearch(int start, int end) {
        if(start>end) return;
        int mid = (start+end)/2;
        int cnt= 0;
        for (int i = 0; i < n; i++) cnt+= arr[i]/mid;

        if(cnt >= m) {//오른쪽
            if(result < mid) result=mid;
            binarySearch(mid+1, end);
        }else{//왼쪽
            binarySearch(start, mid-1);//왼쪽
        }

    }
}

테스트케이스 예시

3 10
1 2 3 4 5 6 7 8 9 10

 

첫번째시행->	우측->	우측->	좌측(start>end이므로 종료)
start = 1 end = 10 mid: 5 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 1 cnt = 2 cnt = 3 cnt = 4 cnt = 5 cnt = 7	start = 6 end = 10 mid: 8 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 1 cnt = 2 cnt = 3	start = 9 end = 10 mid: 9 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 1 cnt = 2	start = 9 end = 8

----------------
result : 8