[백준] 기타 레슨(2343)

문제 링크 : [백준] 기타 레슨(2343)

문제 설명

N개의 수를 가진 배열이 주어지고, 구간의 수 M이 주어집니다.
배열의 연속한 구간을 M개의 구간으로 나누었을 때, 구간의 합 중 최대값이 최소가 되는 값을 구하세요.

입력

N(배열의 크기, 1 <= N <= 100,000)
M(구간의 수, 1 <= M <= N)
A_i(배열의 값, 1 <= A_i <= 10,000)

9 3
1 2 3 4 5 6 7 8 9

출력

17

카테고리

#이분탐색

시간 복잡도 상한

O(NlogN)

해결 방법

1. 모든 경우의 수를 구하기에는 구현도 복잡하고 딱 봐도 시간 복잡도가 안 나올것 같습니다.
2. 그럼 거꾸로 구간의 최대값을 정하고, 각 구간들을 그 최대값이 넘지 않도록 하면서 몇개의 구간으로 나눌 수 있는지를 확인합니다.
3. 구간을 나눌 수 있다면, 최대값을 더 작게 해보고, 나눌 수 없다면, 최대값을 더 크게 해야 될 것입니다.
4. 여기서 구간의 최대값이 증가할 수록, 구간의 갯수는 동일하거나 적어지게 됩니다. 즉, 비 오름차순으로 정렬된 값으로 볼 수 있습니다.
5. 3,4의 내용을 가지고 파라메트릭 서치로 문제를 풀 수 있습니다.
6. 단, 최소값은 주어진 값들 중 최대값보다 작아질 수 없음을 주의해야합니다.

시간복잡도

O(NlogN)

코드

#include<iostream>
using namespace std;
int n,m,d[100000],l,r,x,i,c,s,a;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(i=0;i<n;i++)cin>>d[i],r+=d[i],l=l<d[i]?d[i]:l;
    while(l<=r){
        x=(l+r)/2;
        for(s=c=i=0;i<n;i++){
            if(s+d[i]>x)c++,s=0;
            s+=d[i];
        }
        if(c<m)a=x,r=x-1;
        else l=x+1;
    }
    cout<<a;
}