백준 16401번 : 과자 나눠주기 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

과자 나눠주기 실버 2

 

📖 문제

 

이 문제는 조카에게 최대한의 막대 과자 길이를 균등하게 나눠주는 것이 목표이다. 

 

그러기 위해서는 적절한 과자길이를 찾아야하는데 여기서 이분탐색을 활용한다. 

문제에서 알려줬듯이 과자를 하나로 합칠 순 없다. 

 

예제 2번을 보면 왜 7인지 의문을 품을 수도 있다. 

길이가 8이면 2 2 7 로 합치면 11이되는데 문제에서 여러 조각으로 나눠질 수 있지만 하나로 합칠 수 없다. 라고 나왔기에

합치면 안된다.

 

이분탐색으로 적절한 길이를 찾고, 각 막대과자를 탐색한 길이로 나눈 개수가 조카M명을 넘는지 안넘는지 비교하면서 

찾으면 된다. 

 

나눠줄 수 없다면 0을 출력한다. 

5 3
1 1 1

 이런 경우 0이다.

---

🔅 문제 풀이

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());

        st = new StringTokenizer(br.readLine());
        int[] snacks = new int[n];
        int max = 0;

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

        int front = 1, back = max;
        int size = -1;
        while (front <= back) {

            int mid = (front + back) >>> 1;
            int count = 0;

            // 과자 나누기
            for (int snack : snacks) {
                count += snack / mid;
            }

            // 나눈 과자 개수가 조카 M명보다 많거나 같다면 과자길이를 더 늘림
            if (count >= m) {
                size = mid;
                front = mid + 1;
                // 나눈 과자 개수가 조카 M명보다 적다면 과자 길이를 줄임
            } else {
                back = mid - 1;
            }
        }

        System.out.println(size == -1 ? 0 : size);
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.