[C++][BOJ] 2343 기타 레슨 (feat. 이분탐색)

 

[문제]

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

 

N 개의 강의가 주어질 때 강의들을 몇개씩 엮어서 블루레이로 만들어서 판매하려고 한다.

강의들을 엮을 때 강의의 순서가 바뀌면안되고, 블루레이의 크기는 모두 같아야 한다.

즉, 강의를 쪼갤 수 있는 최소합을 찾자.

 

*문제조건

강의의 수  N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)

각 강의의 길이는 10,000분을 넘지 않는다.

 

[예시]

9 3
1 2 3 4 5 6 7 8 9

17

 

강의는 총 9개이고, 블루레이는 총 3개 가지고 있다.

 

1번 블루레이에 1, 2, 3, 4, 5

2번 블루레이에 6, 7

3번 블루레이에 8, 9

 

을 넣으면 각 블루레이의 크기는 15, 13, 17이 된다.

 

블루레이의 크기는 모두 같아야 하기 때문에 블루레이의 크기는 17이 된다.

17보다 더 작은 크기를 가지는 블루레이를 만들 수 없다.

 

[풀이]

강의의 수가 N (1 ≤ N ≤ 100,000)이고 블루레이의 수 M (1 ≤ M ≤ N) 값을 가지므로

단순하게 풀면  NC1 + NC2 + NC3 + ... + NCN = 2^N -1로 매우 큰 수가 되어 시간초과가 발생한다.

따라서 탐색 수를 줄일 수 있는 이분탐색을 이용해야 한다.

 

이분탐색은 정렬 후, 탐색의 최소값과 최대값을 정해두어야 한다.

블루레이 최소값 : 가장 긴 강의의 길이

블루레이 최대값 : 모든 강의 길이의 합

 

블루레이가 가질 수 있는 최소값과 최대값의 중간값을 정답으로 미리 지정해두고 강의가 나눠지는지 판단한다.

 

즉,

중간값 = (최소값 + 최대값) / 2

 

1) 1번 강의부터 강의들의 합의 중간 값보다 커질 때까지 강의의 수를 더한다.

2) 중간값을 넘어가면 1을 카운트하고 강의 합을 0으로 리셋하고 강의를 다시 더한다.

3) 마지막 강의까지 합을 구했으면 카운트값을 기준으로 최소값, 최대값을 갱신한다.

    3-1) 카운트 값 < 블루레이 개수 이면, 더 작은 크기 값으로 쪼개야 하므로 최대값 = 중간값 -1 로 두고 다시 탐색한다.

    3-2) 카운트 값 > 블루레이 개수 이면, 더 큰 크기 값으로 쪼개야 하므로 최소값 = 중간값 + 1 로 두고 다시 탐색한다.

 

 

[코드]

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

int main() {
    int lectureNum, bluerayNum, input;
    int l, r = 0, mid = 0; // left, right, mid
    vector<int> lectures;

    // 1. Input
    cin >> lectureNum >> bluerayNum;
    for (int i = 0; i < lectureNum; i++) {
        cin >> input;
        lectures.push_back(input);
        r += input;
    }

    // 2. SearchByBinary
    l = *max_element(lectures.begin(), lectures.end());

    while (l <= r) {
        mid = (l + r) / 2;

        int sum = 0, count = 0;
        for (int i = 0; i < lectureNum; i++) {
            if (sum + lectures[i] > mid) {
                count++;
                sum = 0;
            }
            sum += lectures[i];
        }
        if (sum != 0) count++;

        if (count > bluerayNum) l = mid + 1;
        else  r = mid - 1;
    }

    // 3. Output
    cout << l << "\n";

    return 0;
}

 

 

[반례]

7 7
5 9 6 8 7 7 5

answer: 9

 

4 3
99 1 99 1

answer: 100