백준 s2 16401 과자 나눠주기 c++

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

16401번: 과자 나눠주기

 

문제 설명과 풀이는 https://kyj0032.tistory.com/52 참고, 거의 유사함.

다만 랜선 자르기 문제는 불가능한 경우의 수가 없었지만, 이 문제는 0을 출력해야 함.

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

 

코드

/*boj s2 16401 과자 나눠주기*/
#include <algorithm>
#include <iostream>
#define MAXN 1000010
using namespace std;

int M, N;
long long snack[MAXN];

int cut(long long x) {
    int sum = 0;
    for (int i = 0; i < N; i++) {
        sum += snack[i] / x;
    }

    return sum;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> M >> N;
    for (int i = 0; i < N; i++)
        cin >> snack[i];

    long long st = 1;
    long long en = 1000000000;

    long long mid;

    while (st < en) {
        mid = (st + en + 1) / 2;
        int res = cut(mid);

        if (res < M)
            en = mid - 1;
        else
            st = mid;
    }

    int res = cut(st);
    if (res < M)
        st = 0;
    cout << st << "\n";
}