[BAEKJOON] 16401 과자 나눠주기 (C++)

[ 문제 ]

[ 조건 ]
최대한 긴 과자를 나눠줘야 될 것!

나눈 과자를 합칠순 없음 = 막대과자 1개는 1번사용하면 끝임.

[ 순서 ]

구해야 할 결과값이 "막대과자의 길이"이므로 막대과자 길이에 대해 이분탐색을 진행함

막대과자의 길이가, 모든 막대과자와 비교했을때 조각으로 나눠지는 경우를 전부 더해주어

이 값이 아이들의 수와 맞는지 비교하면됨.
[ 핵심소스코드 / C++ ]

// 이분탐색
while (left <= right) {
    int mid = (left + right) / 2;
    if (result) {		 	// 결과값이 작다면
        right = mid - 1;
    }
    else {				// 크거나 같다면
        res = res > mid ? res : mid;	// 최대치 저장
        left = mid + 1; 
    }
}

[ 전체소스코드 / C++ ] 

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

#define MAX 1000001

int child, s;
int snak[MAX];
int res;
int give(int mid) {
    int result = 0;
    for (int i = 0; i < s; i++)
        result += snak[i] / mid;
    return result < child;
}

void solve() {
    int left = 1, right = snak[s - 1];
    while (left <= right) {
        int mid = (left + right) / 2;
        if (give(mid)) { 
            right = mid - 1;
        }
        else {
            res = res > mid ? res : mid;
            left = mid + 1; 
        }
    }
    cout << res;
}
int main() {
#ifdef _CONSOLE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> child >> s;
    for (int i = 0; i < s; i++)
        cin >> snak[i];
    sort(snak, snak + s);
    solve();
}