백준 16401 과자 나눠주기 자바(java)

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

16401번: 과자 나눠주기

 

풀이 방법

이분 탐색을 사용한다.

최악의 경우 조카에게 줄 수 있는 과자의 길이의 경우는 1 이상 10^9 이하가 되므로 완전 탐색하면 시간 초과가 일어난다. 따라서, 시간 복잡도가 O(log n) 로 검색 속도가 더 빠른 이분 탐색을 생각하였다.

 

먼저, 과자 배열을 오름차순 정렬해준다.

다음 이분 탐색에 필요한 left, right 기준은 조카에게 나누어 줄 과자의 길이로 설정한다.

left 는 최소 길이인 1, right는 배열의 마지막 과자 길이 즉, 입력 받은 과자의 최대 길이로 초기화한다.

그 다음 과자의 길이가 중간값 mid 일 때 나누어 줄 수 있는 조카의 수를 구하는 데 과자 배열을 반복문으로 탐색하면서 현재 과자의 길이가 mid 이상이면 과자의 길이를 mid 로 나눈 값을 조카의 수에 더한다.

앞서, 과자 배열을 오름차순 정렬하였기 때문에 뒤에서부터 탐색하여 mid 보다 짧아질 때 탈출해준다.

 

결과적으로 구한 조카의 수가 M 보다 작다면 과자의 길이가 너무 길다는 것이므로 right 를 mid -1 로 하여 과자 길이를 줄여주고, M 이상이면 left 를 mid + 1로 하여 과자 길이를 늘려준다.

 

코드

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

public class Main {

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

        String[] line = br.readLine().split(" ");
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(line[i]);
        }

        Arrays.sort(arr); // 과자 길이 오름차순 정렬

        int answer = 0;
        int left = 1;
        int right = arr[N-1];
        while(left <= right) {
            int mid = (left + right) / 2;

            int cnt = 0;
            for(int i=N-1; i>=0; i--) {
                if(arr[i] < mid) {
                    break;
                }
                cnt += arr[i] / mid;
            }

            if(cnt >= M) { // M명 이상에게 나눌 수 있다면
                answer = Math.max(answer, mid);
                left = mid + 1;
            } else { // M명에게 나누어 줄 수 없을 때
                right = mid - 1;
            }
        }
        System.out.println(answer);
    }
}