[백준] 16401번 - 과자 나눠주기 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 $N$ 개의 과자를 $M$ 명의 조카에게 나눠줄 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구해야 하는 문제다. 이때 과자 길이는 동일해야 하며 합칠 수 없다.

해당 문제는 매개 변수 이분 탐색을 활용하면 해결할 수 있는데 과자 길이의 하한과 상한의 중간 값을 기준으로 과자를 나눠줄 수 있는지 판단하고 나눠줄 수 있으면 나눌 길이를 더 높여서 다시 나눠줄 수 있는지 판단하고 나눠줄 수 없으면 나눌 길이를 줄여서 나눠줄 수 있는지 판단하는 과정을 반복하면 된다. 이 과정을 이분 탐색을 통해 탐색 범위를 반씩 줄여나가면 된다.

이 과정으로 $M$ 개 초과를 만들 수 있는 최소 길이를 찾은 후 $-1$ 을 하면 $M$ 개 이상 만들 수 있는 최대 길이를 구할 수 있다. 이를 위해 Upper Bound 이분 탐색을 기본으로 매개 변수 탐색을 수행했다.

---

2. 코드

1. 이분 탐색 + 매개 변수 탐색 [Java]

자를 길이가 mid 가 된다.

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[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(upperBound(arr, M) - 1);
    }

    static int upperBound(int[] arr, int key) {
        int left = 1;
        int right = 1_000_000_001;  // 과자의 길이가 최대 10^9까지라서 right의 상한을 10^9+1로 설정

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

            int cnt = 0;
            for (int n : arr) {
                cnt += n / mid;
            }

            if (cnt >= key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }
}

2. 이분 탐색 + 매개 변수 탐색 [C++]

자를 길이가 mid 가 된다.

#include <bits/stdc++.h>
using namespace std;

int upper_bound_param(const vector<int>& v, int m) {
    int left = 1;
    int right = 1000000001;  // 과자의 길이가 최대 10^9까지라서 right의 상한을 10^9+1로 설정

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

        int cnt = 0;
        for (int n : v) {
            cnt += n / mid;
        }

        if (cnt >= m) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return right;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    cin >> m >> n;

    vector<int> v(n);
    for (int& x : v) cin >> x;

    cout << upper_bound_param(v, m) - 1;
}

---

3. 풀이 정보

1. 이분 탐색 + 매개 변수 탐색 [Java]

언어	시간	메모리	코드 길이
Java 11	532 ms	115124 KB	1151 B

2. 이분 탐색 + 매개 변수 탐색 [C++]

언어	시간	메모리	코드 길이
C++ 17	168 ms	5824 KB	719 B

---