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

문제

https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

풀이

이분탐색 문제이다.

mid 값을 블루레이 중 최소값으로 두고 이분탐색을 수행한다.

 

문제에 주어진 예제로 예를 들면,

9 3
1 2 3 4 5 6 7 8 9

 

mid	16	17	18
구간	[1 2 3 4 5] [6 7] [8 9]  8+9 > 16 => cnt++	[1 2 3 4 5] [6 7] [8 9]	[1 2 3 4 5] [6 7] [8 9]
cnt	3	2	2

 

위와 같이 mid 값이 최소값 이상의 숫자라면 cnt가 M보다 작게 된다.

따라서 ask 함수에서 cnt 값이 M 이하인 경우 True를 반환하고

cnt 값이 M보다 큰 경우에는 False를 반환한 후, mid 값을 키워주기 위해 left=mid+1을 수행한다.

 

하지만 이 방식으로는 아래와 같은 반례를 통과하지 못한다.

7 7
5 9 6 8 7 7 5

따라서 mid 값이 강의 길이 하나보다 작다면 mid 값이 커져야 하므로 False를 리턴하도록 했다.

(블루레이의 크기가 너무 작아서 강의 한 개도 담을 수 없으므로)

 

탐색할 범위는 0 ~ 10^9 으로 설정하여 이분탐색을 수행한다.

코드

#include <iostream>

using namespace std;
int N, M;
int arr[100001];

bool ask(long long mid) {
    int cnt = 1, sum = 0;

    for (int i = 0; i < N; i++) {
        if (arr[i] > mid) return false; // mid 값이 너무 작아서 강의 한 개도 담을 수 없으므로 mid 값을 증가시켜야 함. 
        if (sum + arr[i] > mid) {
            cnt++;
            sum = 0;
        }
        sum += arr[i];
    }
    return cnt <= M;
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    long long right = 1000000000; // 강의 수(10^5)와 강의 길이(10^4)의 최대값의 곱
    long long left = 0;
    long long ans, mid;

    while (left < right) {
        mid = (left + right) / 2;
        if (ask(mid)) {
            ans = mid;
            right = mid;
        } else left = mid + 1;
    }
    cout << ans;
}