[백준] 16401 : 과자 나눠주기 - Java

• 백준 문제 URL

---

문제 요약

막대 과자 n개와 조카 m명이 있다.
과자를 잘라서 조카 한 명당 동일한 길이의 과자 조각을 주되,
한 명당 받는 과자 조각의 최대 길이를 구하는 문제다.

즉,

• 과자 길이 snack[i]를 길이 mid로 자르면 snack[i] / mid 조각 생성
• 총 조각 수가 m명 이상이 되는 최대 mid를 찾는다.

---

핵심 아이디어

"한 명당 동일 길이의 최대 조각" → 이진 탐색으로 조각 길이 결정

핵심은 이진 탐색 범위:

• 최소: 1 (최소 조각 크기)
• 최대: 가장 긴 과자 길이

중간값 mid로 자를 때:

• 총 조각 수 = Σ(snack[i] / mid)
• 조각 수 ≥ m → 더 큰 조각 시도 (start = mid + 1)
• 조각 수 < m → 조각을 작게 해야 함 (end = mid - 1)

---

알고리즘 핵심 로직

1. 최대 과자 길이 찾기 → 이진 탐색 상한
2. start = 1, end = maxSnack
3. while start <= end:
   mid = (start + end) / 2
   
   count = 0
   for 각 과자:
       count += snack[i] / mid
   
   if count >= m:
       answer = mid
       start = mid + 1
   else:
       end = mid - 1

---

전체 코드 (제출용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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()); // 과자 수

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

        Arrays.sort(snack);
        int startIdx = 1;
        int endIdx = snack[n - 1];
        int answer = 0;

        while (startIdx <= endIdx) {
            int mid = (startIdx + endIdx) / 2;
            int count = 0;

            for (int length : snack) {
                count += length / mid;
            }

            if (count >= m) {
                answer = mid;
                startIdx = mid + 1;
            } else {
                endIdx = mid - 1;
            }
        }

        System.out.println(answer);
    }
}

---

예제 시뮬레이션

입력:

m = 6, n = 6
snack = [19, 10, 12, 32, 26, 48]

정렬 후: [10, 12, 19, 26, 32, 48]

이진 탐색 과정:

mid=24: count = 0+0+0+1+1+2 = 4 < 6 → end=23
mid=12: count = 0+1+1+2+2+4 = 10 ≥ 6 → answer=12, start=13
mid=18: count = 0+0+1+1+1+2 = 5 < 6 → end=17
...
최대 길이 = 15

---

핵심 포인트 정리

• 정수 나눗셈 length / mid 로 조각 수 계산
• 조각 수 ≥ 조카 수 시 최대 길이 탐색
• 시간 복잡도: (O(n \log M))