(C++) - 백준(BOJ) 2343번 : 기타 레슨 답

www.acmicpc.net/problem/2343

2343번: 기타 레슨

이분탐색 문제였습니다. 이분탐색시 pivot역할을 하는 left, right의 초기값과 max값을 잘 생각해 작성해야합니다.

 

풀이방법

 1. 이분탐색시 비교할 초기값 생각하기 : 가장 긴 레슨이 곧 해당 블루레이 길이의 최소가 되므로 이를 left로 두고 right는 블루 레이의 개수가 1개, 10만개의 레슨 개수, 모든 레슨의 길이가 1만일경우 한 블루레이의 길이는 1만 * 10만 = 10000 * 100000 = 1e+9 즉 10억이 됩니다. 

 

 2. 구간 계산하기 : 찾으려는 최소 블루레이 크기를 mid라고 두고 매 mid가 갱신될 때마다 mid에 대해 구간을 계산합니다. 레슨들의 길이를 순서대로 누적해 더한 후 만약 mid보다 sum이 크다면 그 이전까지가 블루레이의 한 구간입니다. 따라서 cnt++해주게되면 전체 레슨에 대한 총 구간 cnt가 나옵니다. 

 

 3. 값들을 갱신하기 : 이 cnt가 m이상이라면 mid의 값이 너무 작아 구간이 m이상으로 잘게 나온 경우이므로 left = mid + 1이 됩니다. 반대의 경우는 구간이 너무 넓어 m보다 작으므로 right값을 mid - 1로 줄여줍니다.

 

 4. left를 반환하여 출력합니다.

Code

#include <bits/stdc++.h>
using namespace std;
int lesson[100001];
int maxLesson = 0;
int n,m;

int getBlueRayCount(int mid){
    int cnt = 0;
    int sum = 0;
    for(int i = 0; i < n; i++){
        sum += lesson[i];
        if(sum > mid) {
            i--;
            sum = 0;
            cnt++;
        }
    }
    return cnt;
}

int binarySearch(){
    int left = maxLesson;
    int right = 1000000000;
    while(left <= right){
        int mid = (left + right)/2;
        int cnt = getBlueRayCount(mid);
        if(cnt >= m) left = mid + 1;
        else right = mid - 1; 
    }
    return left;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> lesson[i];
        maxLesson = max(maxLesson,lesson[i]);
    }
    cout << binarySearch();
}