boj 16401 과자 나눠주기

문제 링크

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

문제 풀이

이분탐색 문제다...
너무 오래만에 보는 이분탐색이라 헷갈렸다..ㅠㅠ
과자 막대 길이를 이분으로 계속 나누면서 나눈 막대 길이 과자로 M명에 조카들에게 나눠 줄 수 있으면 최대 막대 과제 길이를 업뎃해주면서 left=mid+1로 바꿔준다.
아닌 경우에는 right=mid-1로 바꿔준다.

이분 탐색 코드

  		int left = 1;
        int right = arr[n - 1];
        int max = Integer.MIN_VALUE;
        while (left <= right) {
            int mid = (left+right)/2;
            int cnt=0;

            for (int i = 0; i <n ; i++) {
                cnt += arr[i] / mid;
            }
            //과제를 나눠줄수 있다
            if (cnt >= m) {
                max = Math.max(max, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

전체 코드

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 과자나눠주기 {

    static int n,m;
    static int[] arr;
    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);
        int left = 1;
        int right = arr[n - 1];
        int max = Integer.MIN_VALUE;
        while (left <= right) {
            int mid = (left+right)/2;
            int cnt=0;

            for (int i = 0; i <n ; i++) {
                cnt += arr[i] / mid;
            }
            //과제를 나눠줄수 있다
            if (cnt >= m) {
                max = Math.max(max, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(max==Integer.MIN_VALUE?0:max);

        }

}