[BOJ 2343] 기타 레슨

문제 출처 : https://www.acmicpc.net/problem/2343

 

풀이 :

 

이분 탐색 문제입니다.

블루레이의 길이를 기준으로 이분탐색을 돌아 가능한 모든 경우의수를 다 시도해봅니다.

이분 탐색을 돌 때 left와 right를 기준으로 도는데,

1. Mid 값이 문제조건을 만족 할 때, (즉, Mid값을 블루레이의 길이로 잡고 M을 채울때 M개 안에 다 채워 질 때)

 - binary( left , Mid - 1 )

2. Mid 값이 문제 조건을 만족 시키지 못 할 때,

 - binary( Mid + 1, right )

위와 같이 탐색하시면 됩니다.

O(n) * O(logn) 으로 총 O(nlogn)의 시간복잡도를 가집니다.

 

#include<stdio.h>
#define MIN(A,B) ((A) > (B) ? (B) : (A))
 
int arr[100001], marr[100001], n, m, Max, Min = 987654321;
 
void binary(int l,int r)
{
    if (l > r)return;
    int mcnt=0,type=0;
 
    int mid = (r + l) / 2;
    for (int i = 0; i < n&&!type; i++)
    {
        if (marr[mcnt] + arr[i] > mid)
        {
            marr[mcnt] = 0;
            mcnt++;
        }
        if (mcnt == m||arr[i]>mid)type++;
        else marr[mcnt] += arr[i];
    }
    if (!type)
    {
        marr[mcnt] = 0;
        Min = MIN(Min, mid);
        binary(l, mid - 1);
    }
    else binary(mid + 1, r);
}
 
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
        Max += arr[i];
    }
    binary(1,Max);
    printf("%d", Min);
}