[백준/Baekjoon] 16401 과자 나눠주기 C++ :: Binary Search

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

16401번: 과자 나눠주기

---

1. Logic

스탠다드한 이분탐색 문제이다. 

중앙값을 구한 뒤 입력 받은 사탕들 중에서 나눗셈연산자로 사탕의 갯수를 구해주면 된다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int nephew, cookie;

vector<int> input;

bool check(int val) {
    int ret = 0;

    if(nephew < cookie) {
        for(int i = cookie - nephew - 1; i < cookie; i++) {
            ret += input[i] / val;
        }
    }
    else {
        for(int i = 0; i < cookie; i++) {
            ret += input[i] / val;
        }
    }
    
    if(ret >= nephew) {
        return true;
    }
    else return false;
}

int binarySearch() {
    int maxLength = 0;
    int left = 1;
    int right = input[cookie - 1];
    int mid;

    while(left <= right) {
        mid = (left + right) / 2;

        if(check(mid)) {
            maxLength = mid;
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return maxLength;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> nephew >> cookie;

    for(int i = 0; i < cookie; i++) {
        int a;
        cin >> a;

        input.push_back(a);
    }

    sort(input.begin(), input.end());

    cout << binarySearch();
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐