[Algorithm] 과자 나눠주기

Jong Min ·2025년 4월 14일

algorithm

Algorithm

목록 보기

17/30

🍭 백준 16401번 - 과자 나눠주기

🔗 과자 나줘주기

📌 문제 설명

명절이 되면 조카들에게 막대 과자를 나눠줘야 한다!

모든 조카에게 같은 길이의 과자를 줘야 한다.
과자는 쪼갤 수는 있지만 붙일 수는 없다.
조카 수 M명, 과자 수 N개가 주어진다.

각 조카에게 줄 수 있는 막대 과자의 최대 길이를 구하자!

🧩 예제 입력 및 출력

// 입력

3 10
1 2 3 4 5 6 7 8 9 10

// 출력
8

💡 문제 핵심

모든 조카에게 같은 길이로 나눠줘야 한다.
가능한 최대 길이를 찾아야 하므로 이진 탐색을 활용한다.

🔍 풀이 아이디어

✅ 핵심 아이디어: 이진 탐색

막대 과자의 최소 길이 1부터, 가장 긴 과자의 길이까지 범위를 잡고 이진 탐색
현재 길이 mid로 모든 과자를 나눠봤을 때, 조카 수 이상이면 가능
그렇다면 길이를 더 늘려보고, 아니면 줄인다

👣 이진 탐색 시뮬레이션

예제: 3 10 / 1 2 3 4 5 6 7 8 9 10

초기 범위:

left = 1, right = 10, result = 0

mid = 5 → 총 6명에게 가능 → ✅
→ left = 6, result = 5
mid = 8 → 총 3명 가능 → ✅
→ left = 9, result = 8
mid = 9 → 총 2명 가능 → ❌
→ right = 8

→ 종료 → 정답은 8

✅ 자바 코드

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

public class Main {
    static int M, N;
    static int[] snacks;

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

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        snacks = new int[N];
        st = new StringTokenizer(br.readLine());
        int maxLen = 0;

        for (int i = 0; i < N; i++) {
            snacks[i] = Integer.parseInt(st.nextToken());
            maxLen = Math.max(maxLen, snacks[i]);
        }

        int left = 1;
        int right = maxLen;
        int result = 0;

        while (left <= right) {
            int mid = (left + right) / 2;

            long count = 0;
            for (int snack : snacks) {
                count += snack / mid;
            }

            if (count >= M) {
                result = mid; // 가능한 길이 저장
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        System.out.println(result);
    }
}