[C++] BOJ 16401 과자 나눠주기

문제

www.acmicpc.net/problem/16401

16401번: 과자 나눠주기

코드

#include <iostream>
using namespace std;
int cookie[1000001];
int m, n, res;

int search(){
    int rt = 1000000000;
    int lt = 1;

    while (lt <= rt) {
        int mid = (lt + rt) / 2;
        int cnt = 0;
        for (int i = 1; i <= n; i++)
            cnt += cookie[i] / mid; 
        //mid길이만큼씩 나눠주면 몇명에게 나눠줄 수 있는지 세기
        if (cnt >= m){
            lt = mid + 1;
            res = mid;
        }
        else if (cnt < m)
            rt = mid - 1;
    }
    return res;
}
int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++){
        cin >> cookie[i];
    }
    cout << search();
}

풀이방법

이분탐색을 이용한다. 각 mid 길이만큼 나눠주면 몇 명에게 나눠줄 수 있는지를 세고, 그 값이 주어진 m보다 크거나 같으면 res값을 갱신하며 mid의 오른쪽에 대해 이분탐색을 진행하고, m보다 작으면 mid의 왼쪽에 대해 이분탐색을 진행한다.

고민과정

처음에 범위설정을 할 때, rt를 입력값 중 최대값으로 하려다가 그냥 입력값으로 가능한 수의 최대값으로 했다.