[ 백준 BOJ ] 2343번 - 기타 레슨(C++)

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

 

생각 흐름

• 이분 탐색을 이용해서 블루레이의 크기를 구해준다.
• 이 블루레이 크기에 맞게 M개 이하로 강의들을 짜를 수 있는지 검증해준다.
• 만약 M개 이하로 강의들을 짜를 수 있다면 블루레이의 크기를 줄여주는 방향으로 다시 탐색하고, M개 초과 일시에는 블루레이킈 크기를 크게 하는 방향으로 다시 탐색해준다.
• 주의할 점으로는 각각의 동영상 크기가 블루레이 크기를 넘어가는지 검증해줘야 한다.

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> v;

int check(int middle){
    int c = 1;
    int s = 0;
    for(int i = 0; i<v.size(); i++){
        if(v[i]>middle){
            return 2100000000;
        }
        if(s+v[i]>middle){
            c++;
            s=0;
        }
        
        s+=v[i];
    }
    
    return c;
}

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

    cin>>N>>M;
    
    for(int i = 0; i<N; i++){
        int tmp;
        cin>>tmp;
        
        v.push_back(tmp);
    }
    
    int s=1,t=10000*100000;
    
    int answer=2100000000;
    
    while(s<=t){
        int middle = (s+t)/2;
        int tmp = check(middle);
        if(tmp<=M){
            answer=min(answer,middle);
            t=middle-1;
        }else{
            s=middle+1;
        }
    }
    
    cout<<answer<<endl;
    
    return 0;
}