[이분탐색 / BOJ 2343 / C++] 기타레슨

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

2343번: 기타 레슨

 

이 문제는 이분 탐색인 걸 모르면 어렵다.

우리가 찾아야할 값(블루레이의 최소 크기)을 key로 두고, 이 값을 계속해서 찾아나가는 형식으로 풀어야한다.

자세한 건 코드를 보며 풀어보자!

 

#include <bits/stdc++.h>

using namespace std;

int N, M, res=INT_MAX;
vector<int> lectures;

bool check(int mid){
    int num=0; // 필요한 블루레이 수
    int nw=0; // 현재 강의 위치
    
    while(nw<N) {
        int size=0;
        
        for(int i = nw ; i < N ; i++){
            size+=lectures[i];
            nw++;
            if(size > mid){
                size-=lectures[i];
                nw--;
                break;
            }
        }
        num++;
    }
    return num <= M; // 주어진 블루레이 수가 M개일때 mid는 가능한 블루레이의 크기를 말함.
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    
    for(int i = 0 ; i < N ; i++){
        int tmp;
        cin >> tmp;
        lectures.push_back(tmp);
        
    }
    int mid=0;
    int lo = *max_element(lectures.begin(), lectures.end()); // 최대값
    int hi = accumulate(lectures.begin(), lectures.end(), 0); // 합
    
    while (lo <= hi) {
        mid = (lo+hi)/2;
        if(check(mid)){
            res = min(res, mid);
            hi = mid - 1;
        }else{
            lo = mid + 1;
        }
    }
    
    cout << res << '\n';
    
    
}

// 40분 소요
// check(mid)의  return num <= M; 의 의미를 기억하자