16401번. 과자 나눠주기

 

아이디어

조카에게 나눠줄 막대 과자의 길이를 X 라고 하면 나눠줄 수 있는 과자의 개수는 

 

sum(L1 / X, L2 / X, ..., LN / X)

 

이다.

 

만약 위의 값이 조카의 수 M 보다 작으면 과자의 길이 X 가 너무 길다는 의미이므로 과자의 길이를 줄이고, M 보다 크면 과자의 길이 X 가 너무 작다는 의미이므로 과자의 길이를 늘려야 한다.

 

따라서 이분탐색을 통해 문제를 해결할 수 있고 막대 과자의 최대 길이를 출력해야 하므로 위의 값이 == M 이 되는 상황에서도 과자의 길이 X 를 늘려서 최대 길이를 구하면 된다.

 

 

풀이코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        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[] snacks = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            snacks[i] = Integer.parseInt(st.nextToken());
        }

        int start = 1;
        int end = 1_000_000_000;

        while (start <= end) {
            int len = (start + end) / 2;

            int cnt = 0;
            for (int i = 0; i < N; i++) {
                cnt += snacks[i] / len;
            }

            if (cnt < M) {
                end = len - 1;
            } else {
                start = len + 1;
            }
        }

        System.out.println(start - 1);
    }
}