[ 백준 / C++ ] 2343 : 기타 레슨

[ 문제 ]

 

2343번: 기타 레슨 (acmicpc.net)

 

[ 접근방법 ]

 

블루레이 크기를 기준으로 이분탐색을 진행한다.

 

블루레이 크기가 제일 작을 때는 m = n일 때이고,

블루레이 크기가 제일 클 때는 m = 1일 때이다.

 

각각의 경우를 계산하여 l과 r에 저정한 후, 아래의 while문과 같이 이분탐색을 진행한다.

 

만약 블루레이 개수가 m보다 크면 블루레이 크기를 늘려서 개수를 줄여야 하고, 그래서 l을 조정한다.

블루레이 개수가 m보다 작으면 반대로 r을 조정한다.

 

while문 마지막에 l, r 조정하는 부분을 신경써줘야 한다. (자칫하다가는 무한루프)

 

연속된 수가 l, r에 들어있으면 (l + r) / 2는 l과 똑같이 나온다.

l = (l + r) / 2

r = (l + r + 1) / 2 = l + 1 

 

우리는 검사를 (l + r) / 2로 하고 있다.

 

연속된 수가 들어갔을 때 블루레이 개수(cnt)가 m보다 크면 l을 늘려야 한다.

따라서 l을 (l + r + 1) / 2로 바꾼다.

 

연속된 수가 들어갔을 때 블루레이 개수(cnt)가 m보다 작으면 r을 줄여야 한다.

따라서 r을 (l + r) / 2로 바꾼다.

 

연속된 수가 들어갔을 때 블루레이 개수(cnt)가 m이랑 같으면 (l + r) / 2 = l이 정답인 것이다.

따라서 r을 (l + r) / 2로 바꾼다.

 

[ 소스코드 ]

 

#include <iostream>
#include <algorithm>

using namespace std;

int n, m, arr[1000010], l, r;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        l = max(l, arr[i]);
        r += arr[i];
    }

    while (l < r)
    {
        int cnt = 1, sum = 0;
        for (int i = 0; i < n; i++)
        {
            if (sum + arr[i] > (l + r) / 2)
            {
                cnt++;
                sum = 0;
            }
            sum += arr[i];
        }

        if (cnt > m)
            l = (l + r + 1) / 2;
        else
            r = (l + r) / 2;
    }

    cout << l;

    return 0;
}