✅ 이분탐색

문제

1. 해결 로직

• 블루레이 크기는 1에서 모든 강의 길이의 합 사이이다.
• 각 강의의 최대 길이는 10,000을 넘지 않고 강의의 수는 최대 100,000이므로 1부터 10,000 * 100,000 까지 증가시키거나 감소시키면서 가능한 블루레이의 크기 중 최소를 구할 수 없다. (시간초과)
• 따라서 이진탐색을 사용한다.

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int N, M, ans;
vector<int> lec;

int l,r,m;

bool is_possible(){
    
    int sum=0, cnt=1;

    for(int i=0;i<N;i++){
        if(lec[i] > m) return false;
        sum += lec[i];
        if(sum > m){
            cnt ++;
            sum = lec[i];
        }        
    }
    
    if(cnt <= M) return true;
    else return false;
}

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

    cin >> N >> M;
    for(int i=0;i<N;i++){
        int tmp;
        cin >> tmp;
        lec.push_back(tmp);
        r+=tmp;
    }

    while(l <= r){

        m = (l+r)/2;

        if(is_possible()){
            r = m - 1;
            ans = m;
        }
        else{
            l = m + 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

3. 시간 복잡도

$O(logN)$

4. Review

is_possible()을 잘 판별하는지 반례를 넣어봐야 하는데
반례를 찾기가 힘들었다..

그리고 하나의 강의는 블루레이의 크기보다 클 수 없다. (담을 수 없으면 안됨)

if(lec[i] > m) return false;

5. Reference

https://imnotabear.tistory.com/38

반례 참고
https://bingorithm.tistory.com/10