(매일 BOJ) C++ 16401번 과자 나눠주기

이번 문제는 16401번 과자 나눠주기 문제이다.

접근법

1. 어떤 길이 L로 자를 경우, 각 과자로 만들 수 있는 조각 수는 과자 길이 / L이다.
2. 모든 과자에 대해 이 값을 합산한 결과가 M 이상이면 해당 길이로 나눠주는 것이 가능하다.
3. 이분 탐색을 통해 가능한 최대 길이 L을 찾는다.

알고리즘 설계

1. 입력된 과자 길이를 배열에 저장한다.
2. 탐색 범위는 start = 1부터 end = max(과자 길이)까지로 설정한다.
3. 이진 탐색을 수행하며, mid를 현재 시도하는 과자 길이로 간주한다.
4. 각 과자마다 길이 / mid를 계산하여 총 몇 개의 조각을 만들 수 있는지 확인한다.
5. 총 조각 수가 M 이상이면 길이를 더 늘려볼 수 있으므로 start = mid + 1, 답을 갱신한다.
6. 그렇지 않다면 end = mid - 1로 범위를 줄인다.

작성코드

# include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    long long M,N;
    cin >> M >> N;
    vector<long long> v;

    for (int i  = 0; i < N; i++){
        int num;
        cin >> num;
        v.push_back(num);
    }

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

    long long start = 1, end = v.back();
    long long answer = 0;
    while(start <= end){
        long long mid = (start + end) / 2;
        int count = 0;
        for (int i = 0; i < N; i++){
            count += v[i] / mid;
        }

        if (count >= M){
            
            start = mid + 1;
            answer = mid;
        }
        else{
           end = mid - 1; 
        }

    }
    cout << answer;
}