[C++] BOJ 2343 기타 레슨

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

 

[English]

Gang-to wants to sell his own Guitar-lesson videos by making them into Blu-ray. In Blu-ray, total of N lessons need to be saved, but when recording Blu-ray, the order of the lessons must not be switched. When the order gets swapped, it makes the students confused. So, in order to record i-th and j-th lesson in the same blu-ray, all of the lessons between i-th and j-th video must be recorded too.

Because Gang-to does not know how many of the Blu-ray will be sold, he tries to reduce the counts of the Blu-rays. After thinking for a long time, Gangto will use M Blu-rays in order to re ord all of the Guitar videos. In this case, Blu-ray's size (recordable length) needs to be shortest as possible. However, all M must be the same size.

Gang-to's video's length is given in minutes. Find the Blu-ray's size when it is the smallest.

 

[Input]

In the first row, number of lessons N and M will be given. 

On the Next row, Gang-to's guitar lessons will be given in minutes. Each lesson doesn't go over 10,000 minutes.

 

[Output]

Return the smallest size of the Blu-ray.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector <int> nums;
    int temp;
    for (int i=0;i<n;i++){
        cin>>temp;
        nums.push_back(temp);
    }
    long long left=*max_element(nums.begin(),nums.end());

    long long right=100000*10000;
    while (left<=right){
        long long mid=(left+right)/2;
        temp=1;
        long long oneset=0;
        for (int i=0;i<n;i++){
            if (oneset+nums[i]<=mid){
                oneset+=nums[i];
            }
            else{
                oneset=nums[i];
                temp+=1;
            }
        }
        if (temp<=m){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
    }
    cout<<left;
}

 

이 문제는 이분 탐색을 통해서 해결하였다.

제일 핵심적인 부분은, blu-ray의 최소 가능 크기를 10000이 아니라 10000*100000로 해야한다는 사실이다.

100000개의 강의가 10000분동안 일어나는 경우도 있을 수 있기 때문이다.

 

vector를 이용하여 시간들을 저장한다.

또한, vector의 제일 큰 element를 구하기 위해서는 max_element를 이용해야 한다.

max_element는 가장 큰 값의 이터레이터를 반환하고, *max_element는 가장 큰 값의 value를 반환한다.

0부터 10000*100000까지 이분탐색을 통해, 가능한 값들 중 가장 작은 값을 찾는다.

최소한 한 개의 blu-ray는 써야 하기에, size가 mid일때 써야하는 blu-ray의 개수인 temp를 1로 설정하였다.