[BOJ] 백준 16401 - 과자 나눠주기 풀이

1. 문제

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

16401번: 과자 나눠주기

 

2. 풀이

백준 알고리즘 분류에서 이분 탐색으로 분류되어 있다.
과자의 길이는 양의 정수이므로 막대과자의 초기 값은 1로 잡고 이분 탐색을 실시한다.
mid 값을 구한 후 입력으로 주어진 과자 길이를 탐색하면서 탐색한 값을 mid 값으로 나눈 몫을 cnt에 더한다.
이 cnt의 값이 입력으로 주어진 조카의 수보다 크거나 같으면 결과 값에 mid 값을 넣어주고 first에 mid + 1을 넣어준다.
만약 cnt의 값이 입력으로 주어진 조카의 수보다 작으면 과자의 값을 크게 잡은 것이므로 last에 mid - 1을 넣어준다.

 

3. 소스 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken()); // 조카 수
        int N = Integer.parseInt(st.nextToken()); // 과자 수

        int[] snackArr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            snackArr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(snackArr);

        int first = 1;
        int last = snackArr[snackArr.length - 1];
        int mid = 0;
        int result = 0;

        while (first <= last) {
            mid = (first + last) / 2;

            int cnt = 0;
            for (int i = 0; i < snackArr.length; i++) {
                cnt += snackArr[i] / mid;
            }

            if (cnt >= M) {
                result = mid;
                first = mid + 1;
            }

            else {
                last = mid - 1;
            }
        }

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }
}