BOJ 17179: 케이크자르기 (C++)

#include <iostream>
#include <vector>
using namespace std;

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, m,l;
    vector<int> s;
    int tmp;
    cin >> n >> m >> l;
    for (int i = 0; i < m; ++i) {
        cin >> tmp;
        s.push_back(tmp);
    }

    for (int i = 0; i < n; ++i){
        cin >> tmp;

        int low = 0;
        int high = l; //최대 조각 길이
        int mid; // 최소 조각길이의 최댓값

        while (low <= high){
            mid = (low + high) / 2;
            int cut = 0;
            int cutted = 0;
            for (int i = 0; i < m; ++i){
                if (s[i] - cutted >= mid){
                    cut++;
                    cutted = s[i];
                }
            }
            

            if(tmp == cut && l - cutted < mid) { // 같을때 마지막 조각이 mid보다 커야하는데 작으면
                high = mid - 1;
            }
            else if (cut < tmp){
                high = mid - 1;
            }
            else{
                low = mid + 1;
            }
        }
        cout << high << "\n";
    }
}

이분탐색을 이용하면 시간을 초과하지 않고 문제를 풀 수 있다.