[백준 / 실버2] 과자 나눠주기 - JAVA

난이도 : 실버 2

유형 : 이분탐색

구현 시간 : -

문제 링크 : https://www.acmicpc.net/problem/16401

풀이 링크 : https://www.acmicpc.net/source/98101657

풀이 힌트

1. 과자 하나 당 N의 길이를 가진 과자를 만들려면 어떻게 해야 할까?
2. M명의 조카에게 N길이를 가진 과자를 줄 수 있는지 어떻게 판단할 수 있을까?

생각해보기

1. 과자 하나의 길이를 L로 잘라 조카들에게 나누어주려면, 각 과자를 snack / L 개로 나눌 수 있다.
2. 모든 과자에 대해 잘라낸 개수를 합산하면, 총 몇 명의 조카에게 나눠줄 수 있는지가 나온다.
3. 그 개수가 조카 수 M보다 크거나 같으면 길이 L은 가능 → 더 큰 값도 가능한지 확인해야 한다.
4. 반대로 M보다 작으면 길이 L은 불가능 → 더 작은 값에서 찾아야 한다.

👉 따라서 "가능한 최대 과자 길이"를 찾는 전형적인 이분 탐색 문제.

 

* 나눌 수 있는지 어떻게 판단할 수 있을까?

과자 배열 전체에 대해, 과자 하나를 L 길이로 잘라 얻을 수 있는 개수를 합하면 된다.

public static boolean canDivide(int[] snacks, int m, int L) {
        long count = 0;
        for (int snack : snacks) {
            count += snack / L; // 과자 하나를 L 길이로 잘라 얻을 수 있는 개수
        }
        return count >= m; // 조카 m명에게 나눠줄 수 있는지
    }

최종 풀이

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

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());
        int maxSnack = 0;
        for (int i = 0 ; i < N; i++) {
            snacks[i] = Integer.parseInt(st.nextToken());
            maxSnack = Math.max(maxSnack, snacks[i]);
        }

        int low = 1;            // 최소 길이
        int high = maxSnack;    // 최대 과자 길이
        int answer = 0;         // 정답 후보

        while (low <= high) {
            int mid = (low + high) / 2;

            if (canDivide(snacks, M, mid)) {
                answer = mid;   // 가능하다면 답 갱신
                low = mid + 1;  // 더 긴 길이를 시도
            } else {
                high = mid - 1; // 불가능하면 더 짧게
            }
        }

        System.out.println(answer);
    }

    public static boolean canDivide(int[] snacks, int m, int L) {
        long count = 0;
        for (int snack : snacks) {
            count += snack / L; // 과자 하나를 L 길이로 잘라 얻을 수 있는 개수
        }
        return count >= m;
    }
}

트러블슈팅

맨 처음에는 그리디를 이용해서 풀려고 했다. 큰 과자부터 쪼개서 조카에게 나눠주는 방식으로 접근했는데, 반례가 너무 많이 나오고 경우의 수를 일일이 잡아내기 힘들었다. 그래서 이 문제는 그리디로는 풀 수 없다는 것을 깨달았다.

 

이후 다른 풀이를 참고하면서, 이 문제가 사실은 이분 탐색으로 접근해야 한다는 것을 알게 되었다.
처음엔 전혀 이분 탐색 문제처럼 보이지 않았지만, "과자의 길이를 특정해놓고, 그 길이일 때 조건을 만족하는지 확인하는 방식" 으로 생각을 바꾸니 이분 탐색 구조가 자연스럽게 보였다.

즉, 문제에 적힌 설명대로만 보지 않고,

과자의 길이 L을 가정한다 → 조건을 만족하는지 판별한다
라는 관점으로 접근해야 비로소 이분 탐색 문제임을 이해할 수 있었다.