[백준 2343번] 기타 레슨 (C++)

문제링크 : https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, arr[100001];
int l, r;

int main()
{
    ios_base::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 mid = (l+r)/2; //블루레이 길이
        int sum = 0, cnt = 1; //블루레이 갯수 (최소 한개)

        for(int i=0; i<N; i++)
        {
            sum += arr[i];
            if(sum + arr[i+1] > mid)
            {
                sum = 0; //커지면 컷
                cnt++; //블루레이 갯수 증가
            }
        }

        if(cnt > M) l = mid + 1; //블루레이 길이 증가
        else r = mid - 1; //블루레이 길이 감소
    }

    cout << l;

    return 0;
}

 

이분 탐색을 활용한 문제이다.

먼저 l과 r에 대한 최소값과 최대값을 구하여 초기화해준다.

최소값의 경우 배열 내 최대값, 최대값의 경우 배열 내 모든 값의 합이 된다.

 

이후 mid 값을 브룰레이 길이로 잡고 초기화를 시작한다.

추가적으로 구간 체크를 위한 누적합과 블루레이 갯수를 체크할 변수를 선언해준다.

이때 블루레이 갯수를 체크할 cnt는 최소 한개의 블루레이 갯수가 존재하기에 1로 초기화해준다.

 

입력받았던 배열내에 누적합을 구하면서, 해당 누적합 + 다음 값이 현재 mid 값을 넘는지 체크한다.

넘는다면 다음 값까지는 불가능한 것이기에 여기서 sum = 0으로 초기화하여 컷하고, 다음 블루레이로 넘어가는 것이기에 블루레이 갯수를 증가시킨다.

 

이렇게 구한 cnt가 목표 M 보다 크다면 블루레이 길이가 짧아서 갯수가 많은 것이기 때문에 l = mid + 1을 하여 블루레이 길이를 증가시키고, 목표 M 보다 작거나 같다면 블루레이 길이가 길어서 갯수가 적은 것이기 때문에 r = mid - 1을 하여 블루레이 길이를 감소시킨다.