백준 14627번 파닭파닭(JAVA)

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

14627번: 파닭파닭

 

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

이분 탐색을 통해 해당 값(mid)의 길이로 파를 c개 만들 수 있는지를 판단하고 할 수 있다면 start를 늘리고 못한다면 end를 줄여 문제를 해결하였습니다. 

 

package BOJ.binarysearch;

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

public class BOJ_14627 {

    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 s = stoi.apply(st.nextToken());
        int c = stoi.apply(st.nextToken());
        int[] input = new int[s];
        for (int i = 0; i < s; i++) {
            input[i] = stoi.apply(br.readLine());
        }
        long result = binarySearch(input, c);
        System.out.println(result);
    }
    private static final int MAX = 1_000_000_000;
    private static long binarySearch(int[] input, int c) {
        long start = 1;
        long end = MAX;
        long result = 0;
        while (start <= end) {
            long mid = (start + end) / 2;
            if(countOnion(mid,input,c)){
                result = mid;
                start = mid + 1;
            }else{
                end = mid - 1;
            }
        }
        long sum = 0;
        for(int num : input){
            sum += num;
        }
        return sum - result * c;
    }

    private static boolean countOnion(long mid, int[] input, int c) {
        int cnt = 0;
        for(int num : input){
            cnt += num / mid;
        }
        if(cnt >= c){
            return true;
        }
        return false;
    }
}