백준 2343 기타 레슨 (C++)

2343번: 기타 레슨

이분 탐색을 이용한 문제이다. 로직은 주어지는 강의 길이를 모두 더하고 이를 이분 탐색을 하며 최솟값을 구하는 방식이다. 이분 탐색을 진행하면서 반복문을 돌며 mid와 비교하여 카운트를 해준 뒤 카운트가 M보다 크지 않다면 result와 비교하여 작은 수를 저장하고 이를 출력하였다. 이분 탐색이 생각보다 어려웠다. 자주 풀어봐야 겠다.

#include <iostream>

using namespace std;

int N, M;
int A[100000];
int sum = 0;
int result = 987654321;

void binarySearch() {
    int start = 0;
    int end = sum;

    while (start <= end) {
        int mid = (start + end) / 2;
        int cnt = 1;
        int s = 0;

        for (int i = 0; i < N; i++) {
            if (A[i] > mid) {
                cnt = 987654321;
                break;
            }

            s += A[i];
            if (s > mid) {
                s = A[i];
                cnt++;
            }
        }

        if (cnt > M) {
            start = mid + 1;
        }
        else {
            end = mid - 1;
            result = min(result, mid);
        }
    }
}

void solution() {
    binarySearch();

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sum += A[i];
    }

    solution();

    return 0;
}