[BOJ / C++] 2343번 : 기타 레슨

 

문제 링크

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

문제

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

출력

 

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

 

Solved.ac 레벨

골드 V

 

문제 풀이 해설

Do it! 알고리즘 코딩 테스트 C++편 [개정판]에서 '이진 탐색'을 다룰 때 소개된 문제다.

솔직히, 아무런 배경 정보도 없이 이 문제를 보고 이분 탐색을 떠올릴 수 있을지는 모르겠지만...

 

우선, 여기서 우리가 이분 탐색의 대상으로 보아야 하는 것은, 블루레이 디스크 한 개의 크기의 최솟값이다.

 

따라서 이분 탐색의 시작 인덱스는 입력 된 영상의 크기 중 가장 큰 것이 되어야 하고, 끝 인덱스는 모든 영상들의 크기의 합이다.

1개의 디스크에 1개의 영상을 담아 영상의 개수만큼 디스크를 준비한다고 하면, 입력 된 영상의 크기 중 가장 큰 크기를 갖는 영상을 넣을 수 있는 디스크가 필요할 것이고, 1개의 디스크에 모든 영상을 담는다고 하면, 모든 영상들의 크기의 합이 필요하기 때문이다.

 

 

그렇게 한 개의 디스크가 가질 수 있는 크기의 구간이 정해지면, 입력된 영상 리스트를 순회하며 순서대로 한 개의 디스크에 영상을 몇 개 씩 넣을 수 있는지 검토해야 하고, 이때 시작 인덱스가 끝 인덱스보다 커지는 지점이 블루레이 디스크 1개의 크기의 최솟값이다.

 

아래의 규칙을 갖고 이분 탐색을 시작한다.

• mid 지점의 크기로 모든 레슨을 저장할 수 있다면 디스크의 크기가 최소가 아니므로, 끝 인덱스를 mid - 1로 설정하여 범위를 좁힌다.
• mid 지점의 크기로 모든 레슨을 저장할 수 없다면 디스크의 크기가 부족하므로, 시작 인덱스를 mid + 1로 설정하여 범위를 넓힌다.

예제 입출력 1을 가지고 그 값을 구하는 방법을 알아보겠다.

 

레슨 영상의 개수는 9개, 사용하려는 블루레이 디스크의 개수는 3개이며,

순서대로 레슨 영상의 크기는 [1, 2, 3, 4, 5, 6, 7, 8, 9]이다.

 

앞으로 시작 인덱스는 s, 끝 인덱스는 e, 중간 인덱스는 mid라고 표현하겠다.

이 경우 s는 리스트의 최대값인 9가 될 것이고, e는 리스트의 총합인 45가 된다.

가장 처음 상태에서, 1~6번 레슨 영상까지의 합은 21이므로 mid 크기 이내다. 1개의 디스크에 답을 수 있다.

그리고 다음 7~9번 레슨 영상까지의 합은 25이므로 mid 크기 이내다. 따라서 총 2개의 디스크에 모든 영상을 담을 수 있다.

헌데, 우리는 3개의 디스크를 사용해야 한다.

따라서 mid 크기의 디스크로 모든 레슨 영상을 저장할 수 있기에 e의 범위를 줄여준다.

 

변화된 e에 따른 상태는 위의 이미지와 같다.

주어진 3개의 디스크에 모든 레슨 영상이 담겼다.

그럼에도 여전히 지금이 최소인지 명확하지 않으며, mid 크기의 디스크로 모든 레슨 영상을 저장 가능하기 때문에 다시 e의 범위를 줄여준다.

 

그 다음의 경우 mid 크기의 디스크 3개로 모든 레슨 영상을 저장할 수 없다.

그렇다면 s를 mid + 1로 늘려 디스크 크기의 최솟값 범위의 시작점을 오른쪽으로 밀어준다.

 

 

mid가 14로 늘어났지만, 여전히 14 크기의 디스크 3개로 모든 레슨 영상을 저장하는 것은 불가능하다.

다시 시작 인덱스를 오른쪽으로 밀어준다.

 

 

mid가 15로 늘어났음에도 여전히 mid 크기로 모든 영상을 담을 수가 없다.

s를 다시 오른쪽으로 민다.

 

 

하지만 여전히 mid 크기로 모든 영상을 담을 수 없다.

마지막으로 s를 오른쪽으로 미는 순간, 더 이상 디스크의 크기를 줄이거나 늘릴 수 없어진다.

즉, 17이 이 경우 블루레이 디스크 3개로 모든 레슨 영상을 담을 때 한 개의 디스크의 크기의 최소가 된다.

 

문제 풀이 코드

#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    vector<int> lessons;
    int s = 0, e = 0;

    cin >> n >> m;

    lessons.resize(n);

    for(int i = 0; i < n; i++) {
        cin >> lessons[i];
        s = max(s, lessons[i]);
        e += lessons[i];
    }

    while(s <= e) {
        int sum = 0; //구간의 합
        int cnt = 0; //블루레이 디스크의 개수
        int mid = (s + e) / 2;

        for(int i = 0; i < n; i++) {
            if(sum + lessons[i] > mid) {
                cnt++;
                sum = 0;
            }
            sum += lessons[i];
        }

        // lessons 탐색 후 sum이 0이 아니면 추가로 블루레이 디스크 한 장이 더 필요
        if(sum != 0) cnt++;

        // mid 값으로 모든 레슨 저장 불가
        if(cnt > m) s = mid + 1;
        // mid 값으로 모든 레슨 저장 가능
        else e = mid - 1;
    }

    cout << s << "\n";
    return 0;
}