[백준] 16401번 과자 나눠주기

문제: 16401번: 과자 나눠주기

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <limits>
#include <string>

using namespace std;

int binarySearch(int target, vector<int>& cookies) {
    int st = 1;
    int en = cookies[cookies.size()-1];

    int answer = 0;
    while (st <= en) {
        int tmpCnt = 0;
        int mid = (st + en) / 2;

        for (int i = 0; i < cookies.size(); i++) {
            tmpCnt += cookies[i] / mid;
        }

        if (tmpCnt >= target) {
            answer = mid;
            st = mid + 1;
        }
        else {
            en = mid - 1;
        }
    }
    return answer;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int m, n;
    cin >> m >> n;
    vector<int> cookies(n);
    for (int i = 0; i < n; i++)
        cin >> cookies[i];

    // 걍 이분탐색 돌려여
    sort(cookies.begin(), cookies.end());
    cout << binarySearch(m, cookies);

    return 0;
}

 

음.. 걍 쿠키들을 오름차순으로 정렬해놓고 이분탐색 돌리면 된다.

 

맨 처음 시작할 때 st=1, en=쿠키 중에서 가장 큰 값으로 설정한다. 그 후 st<=en 일 때까지 while 문 돌리면서 mid 값 갱신해주고 계속~~~ 이분탐색 돌리면 된다.

 

마지막에 answer 리턴해주면 간단하게 해결 ~_~