백준 16401번 과자 나눠주기 (JAVA)

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

16401번: 과자 나눠주기

 

저는 이분탐색을 통해 문제를 해결하였습니다.

이분탐색으로 해당 값으로 조카의 수에 맞게 과자를 줄 수 있는지 확인하고 

줄 수 있다면, start = mid + 1, 줄 수 없다면 end = mid - 1로 만들면서 진행하였습니다.

과자는 쪼갤 수는 있지만, 붙일 수는 없기 때문에 각각의 과자에서 mid값을 나누면서 합을 구하여 해당 값으로 몇명까지 줄 수 있는지 확인하였습니다.

 

시간복잡도 O(log n)

 

package BOJ.binarysearch;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_16401 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int peopleCnt = stoi.apply(st.nextToken());
        int snackCnt = stoi.apply(st.nextToken());
        int[] snack = new int[snackCnt];
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < snackCnt ; i++) {
            snack[i] = stoi.apply(st.nextToken());
        }
        int result = binarySearch(snack,peopleCnt);
        System.out.println(result);
    }

    private static int binarySearch(int[] snack, int peopleCnt) {
        int end = 1_000_000_000+1;
        int start = 1;
        int result = 0;
        while(start <= end){
            int mid = (start + end)/2;
            if(checkSnackLengthCnt(snack,mid) >= peopleCnt){
                result = mid;
                start = mid + 1;
            }else{
                end = mid - 1;
            }
        }
        return result;
    }
    private static int checkSnackLengthCnt(int[]snack, int value){
        int sum = 0;
        for(int length : snack){
            sum += length / value;
        }
        return sum;
    }
}