[BaekJoon][2343] 기타 레슨

BAEKJOON ONLINE JUDGE

2343 기타 레슨

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

정답을 찾아가는 이진 탐색 문제이다.

레슨의 길이를 기준으로 블루레이를 만들었을 때 만들 수 있는 블루레이의 개수가 M과 같거나 큰 경우

다시 레슨의 길이를 더 크게 하여 가능 여부를 찾는다.

레슨의 길이가 너무 큰 경우 블루레이의 개수가 M보다 작은 값이 나온다. 그 경우 다시 레슨의 길이를 줄여 탐색한다.

이런 식으로 이진 탐색 가능 여부를 만들어 탐색을 하여

M을 만들 수 있는 가장 작은 레슨의 길이를 찾는다.

#include <stdio.h>
 
int n, m;
int lesson[100001];
int sum[100001];
int min;
 
void bsearch(int start, int end)
{
    int i;
    int cnt = 1;
    int middle = (start + end) / 2;
    int max = 0;
 
    if (start == end) {
        min = start;
        return;
    }
 
    for (i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + lesson[i];
 
        if (sum[i] > middle) {
            cnt++;
            sum[i] = lesson[i];
        }
    }
 
    if (cnt <= m)    bsearch(start, middle);
    else                bsearch(middle + 1, end);
}
 
int main()
{
    int i, j;
 
    scanf("%d %d", &n, &m);
 
    for (i = 1; i <= n; i++) {
        scanf("%d", &lesson[i]);
        sum[i] = sum[i - 1] + lesson[i];
    }
    min = sum[n];
 
    bsearch(0, min);
 
    printf("%d\n", min);
 
    return 0;
}