Parametric Search(츄러스 문제)

츄러스 문제

- N명의 사람이 M개의 츄러스를 동일한 길이로 나누어 가진다.
- input 예시
    - 5명의 사람
    - 3개의 츄러스
    - 츄러스 길이 : 50, 30, 40

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

public class Churros {
    static int churros_cnt;
    static int person_cnt;
    static int[] churros;

    public static int Solution() {
        int st = 0;
        int end = Arrays.stream(churros).max().getAsInt();
        int aws = -1;

        while (st <= end) {
            int mid = (st + end) / 2;
            if (test(mid)) {
                st = mid + 1;
                aws = mid;
            } else {
                end = mid - 1;
            }
        }
        return aws;
    }

    public static boolean test(int mid) {
        int cnt = 0;

        for (int i = 0; i < churros_cnt; i++) {
            cnt += churros[i] / mid;
        }
        if (cnt >= person_cnt) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        person_cnt = Integer.parseInt(br.readLine());
        churros_cnt = Integer.parseInt(br.readLine());

        churros = new int[churros_cnt];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < churros_cnt; i++) {
            churros[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(Solution());
    }
}

 

main : 입출력 담당

test : 매개변수로 받은 값을 사용했을 때, 사람 수만큼 분할할 수 있는지 확인

Solution : test 메서드 호출하며 parametric search를 진행