백준 2343 - 기타레슨 - 이분 탐색

문제

문제링크 : https://www.acmicpc.net/problem/2343

풀이전략

1. 총 N개의 레슨이다. 가능한 최소의 블루레이 개수를 세야한다.
2. 블루레이의 크기보다 기타 레슨 동영상이 클 경우에는 패스해야한다.
3. 블루레이의 크기를 이분 탐색으로 찾아야한다.

코드

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> lesson;
int N, M;

int countOfBluelay(long long val){
    int cnt = 1;
    long long valSum = 0;
    for(int i=0; i<lesson.size(); i++){
        //// 변수 하나가 val보다 클수가 있을때를 주의하기
        if(lesson[i] > val) return 2147000000;
        if(valSum + lesson[i] > val){
            valSum = 0;
            cnt++;
        }
        valSum += lesson[i];
    }
    return cnt;
}
int res = 2147000000;
int BinarySearch(long long lt, long long rt){
    if(lt>rt){
        return res;
    }
    else{
        long long mid = (lt+rt)/2;
        int midVal = countOfBluelay(mid);

        if(midVal <= M){
            if(mid < res) res = mid;
            return BinarySearch(lt, mid-1);
            
        }
        else{
            return BinarySearch(mid+1, rt);
        }
    }
}

int main(){

    // freopen("../input.txt","rt",stdin);
    
    scanf("%d %d",&N, &M);
    int tmp;
    long long m = 0;
    for(int i=0; i<N; i++){
        scanf("%d",&tmp);
        m += tmp;
        lesson.push_back(tmp);
    }
    printf("%d\n",BinarySearch(1, m));
    return 0;
}

소감

문제에서 디스크의 크기를 찾아야하는 것이 이번에 이분탐색으로 찾아야하는 목표이다. 지금까지 BFS, DFS, DP, 이분 탐색을 잘 정할 수 있어야한다.