[백준_16401] 과자 나눠주기

문제

백준 16401번
https://www.acmicpc.net/problem/16401

명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.

조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.

그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.

M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.

단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.

첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,000,000,000) 를 만족한다.

첫째 줄에 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 출력한다.

단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다.

• 생각해보기
  
  

Code

• 과자의 길이 배열 중 가장 긴 max 값을 찾는다.
• 문제의 과자 길이 최소값은 1이기 때문에 left는 1, right 값은 max로 잡는다.
• 그리고 mid 를 구한 후 길이 배열에 들어있는 원소들을 mid로 나눈 몫의 값을 cnt에 더해준다.
• cnt와 M(조카 수)를 비교해 cnt가 M(조키 수)보다 같거나 크면 result값을 업데이트 시켜주고 left값을 mid + 1로 업데이트 한다.
• 반대로 cnt가 M(조키 수)보다 작다면 right 값을 mid - 1로 업데이트 한다.
• 이후 left가 right보다 커질 때까지 반복한다.
• 그리고 while문 탈출 후 result값으로 최종 반환한다.

조카 수 3명, 과자 10개일 경우

조카 수 4명, 과자 3개일 경우

Java

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken()); // 조카 수
        int N = Integer.parseInt(st.nextToken()); // 과자 수
        int[] L = new int[N]; // 과자의 길이를 담을 배열
        st = new StringTokenizer(br.readLine());
        int max = 0; // 길이 최대값
        for (int i = 0; i < N; i++) {
            L[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, L[i]);
        }

        System.out.println(binarySearch(L, M, 1, max));;
    }

    public static int binarySearch(int[] L, int M, int left, int right) {
        int result = 0;
        while (left <= right) {
            int mid =  left + (right - left) / 2;
            int cnt = 0;

            for (int i = 0; i < L.length; i++) {
                // 중앙값으로 과자의 길이를 나누어 나오는 갯수 파악
                cnt += L[i] / mid;
            }

            if (cnt >= M) {
                // 위에서 나눈 갯수가 조키수보다 같거나 많을 경우
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}