백준 - 2343 기타 레슨

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

2343번: 기타 레슨

 

이분 탐색!

 

 

 

 

 

 

#include <iostream>
#include <vector>

using namespace std;

inline long long countBlueRay(const vector<int>& lesson, long long mid) {
    long long cnt = 1;
    long long temp = mid;
    for(const auto& el : lesson) {
        if(temp - el < 0) {
            temp = mid - el;
            cnt++;
        } else {
            temp -= el;
        }
    }
    if(temp < 0) cnt++;

    return cnt;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> lesson(N);
    long long low = 0;
    for(int i = 0; i < N; i++) {
        cin >> lesson[i];
        if(low < lesson[i]) {
            low = lesson[i];
        }
    }

    long long high = 1000000000;
    long long mid, result;

    while(low < high) {
        mid = (low + high) / 2;

        long long blueRayNum = countBlueRay(lesson, mid);

        if(blueRayNum > M) {
            low = mid + 1;
        } else {
            result = mid;
            high = mid;
        }
    }

    cout << result;

    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~