2343번_기타 레슨_BOJ

문제 링크

2343번 기타 레슨 : https://www.acmicpc.net/problem/2343

문제 설명 및 해결 아이디어

Parametric Search문제이다.

left의 범위는 레슨 중 가장 긴 길이부터 시작하면 된다.

mid를 lesson길이로 설정한다.

만들어진 블루레이 개수가 M보다 클 경우, mid를 크게하여 블루레이 개수를 줄인다.

만들어진 블루레이 개수가 M보다 작거나 같을 경우, mid를 작게하고, 이때의 mid값 중 최소값을 저장한다.

코드

#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long int
#define MAX_S 100001
ll n, m, maxv, res;
ll lesson[MAX_S];
 
void func() {
    ll left = maxv, right = 1000000000;
    ll sum, cnt;
    while (left <= right) {
        ll mid = (left + right) / 2;
        sum = 0, cnt = 0;
 
        for (int i = 0; i < n; ++i) {
            if (sum + lesson[i] > mid) {
                cnt++;
                sum = 0;
            }
            sum += lesson[i];
        }
        if (sum != 0)
            cnt++;
 
        if (cnt <= m) {
            right = mid - 1;
            res = min(res, mid);
 
        }
        else if (cnt > m) {
            left = mid + 1;
        }
    }
}
 
int main() {
    scanf("%lld %lld", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &lesson[i]);
        maxv = max(maxv, lesson[i]);
    }
    res = 9999999999999999;
    func();
    printf("%lld\n", res);
 
 
    return 0;
}