(매일 BOJ) C++ 2343번 기타 레슨

이번 문제는 2343번 기타 레슨 문제이다.

접근법

이 문제는 흔히 말하는 이분 탐색으로 정답을 찾는 문제 이다.
즉, 정답이 될 수 있는 범위를 두고, 그 안에서 가능한지 아닌지를 판별하면서 범위를 좁혀나가는 방식으로 해결해야 한다.

따라서 이 문제에서는 블루레이 크기를 정해놓고, 그 크기로 강의들을 나눴을 때 M개 이하로 블루레이가 필요한지 확인해야 한다.

 

여기서 이분탐색의 시작과 끝 값은 이러하다.

 

• start = 가장 긴 강의의 길이→ 블루레이 크기는 최소한 이 정도는 되어야 함
• end = 모든 강의의 총합 → 모든 강의를 하나에 담는다면 이게 최대

그 후 mid 를 (start + end) / 2 로 설정하고 아래의 의사코드를 구현하면 된다.

for (각 강의) {
    if (현재 누적 + 강의 > mid) {
        블루레이 개수++;
        누적합 초기화;
    }
    누적합 += 강의;
}

 

 

그 후 이분탐색으로 구한 mid 값이 가능한 경우인지 불가능한 경우인지 판단하면 된다.

• 블루레이 개수가 M 이하면: end = mid - 1; // 더 작은값 탐색
• 블루레이 개수가 M 초과: start = mid + 1; // 더 큰값 탐색

 

작성코드

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

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    long long lecture_num , blueray_num;
    cin >> lecture_num >> blueray_num;
    vector<long long> v;
    long long sum = 0;

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

    long long start = *max_element(v.begin(),v.end()), end = sum;
    long long answer = 0;

    while (start <= end){
        long long mid = (start + end) / 2;
        long long count = 1, blueraysum = 0;
        
        for(int j = 0; j < lecture_num; j++){
            if(blueraysum + v[j] > mid){
                count += 1;
                blueraysum = 0;
            }
            blueraysum += v[j];
        }

        if(count <= blueray_num){
            answer = mid;
            end = mid - 1;
        }
        else start = mid + 1;
    }
    cout << answer;

}