백준 16401번 C++ 풀이

https://www.acmicpc.net/problem/16401

16401번: 과자 나눠주기

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	실버 2

문제

명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.

조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.

그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.

M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.

단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.

입력

첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,000,000,000) 를 만족한다.

출력

첫째 줄에 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 출력한다.

단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다.

---

과자의 무작위 길이 k를 M명에게 나눠주기 위해서 N번의 작업을 수행해야 하기 때문에, 선형탐색, 완전탐색으로 진행한다면 O(kN)의 시간 복잡도를 가질 것이다. k ≤ 10^9이고 N ≤ 10^6이기 때문에 시간제한을 가볍게 넘을 것이다. 그렇기 때문에 k를 1부터 10^9까지(정확히는 L1, L2,...,LN중 최댓값) 모두 따지는 것이 아니라, 이분탐색을 통해 k를 탐색하는 횟수를 log(10^9)이하로 낮추면 된다. 1부터 10^9까지 모두 따지면 최대 10^9번의 탐색을 거쳐야 하지만, 이분탐색을 사용하면 약 30번만에 탐색이 끝난다. 이렇게 되면 O(Nlogk)의 시간복잡도를 가지게 되므로, 시간 내에 통과할 수 있다.

 

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

int child, snackCnt;
vector<int> snack;

void input() {
    cin >> child >> snackCnt;
    snack.resize(snackCnt);
    for (int& x : snack) cin >> x;
    sort(snack.begin(), snack.end());
}

int checkCnt(int x) {
    int cnt = 0;
    for (int len : snack) cnt += len / x;
    return cnt;
}

void sol() {
    int st = 1, ed = snack[snackCnt - 1];
    int mid, result = 0;
    while (st <= ed) {
        mid = (st + ed) / 2;

        if (child <= checkCnt(mid)) {
            st = mid + 1;
            result = mid;
        }
        else {
            ed = mid - 1;
        }
    }
    cout << result;
} 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    sol();
}