[BOJ/백준][Silver1] 2343 : 기타 레슨 (C++)

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

2343번: 기타 레슨

 

 

[난이도] Silver1
[유형] 이분탐색

[풀이]
가능한 블루레이 크기의 최솟값은 길이가 가장 짧은 강의의 길이
이고 최댓값은 100000(N의 최댓값) * 10000 (강의 길이의 최댓값) = 10^9
입니다.

범위가 너무 크기 때문에 이분탐색을 이용해서 최솟값을 찾아주면 됩니다.

mid 값을 블루레이의 크기라고 가정 했을 때, bool check(int k) 함수를 이용해서 조건을 만족하는지 체크해주며
범위를 좁혀갈 수 있습니다.

 

#include <cstdio>
int n,m,a[100000];
bool check(int k){
    int cnt=1,sum=0;
    for(int i=0;i<n;i++){
        if(sum+a[i]>k) {
            sum=0;
            cnt++;
        }
        sum+=a[i];
    }
    return cnt <= m;
}
int main(){
    scanf("%d%d",&n,&m);
    int lo=1,hi=1e9+1;
    for(int i=0;i<n;i++) {
        scanf("%d",&a[i]);
        if(a[i]>lo) lo=a[i];
    }
    lo--;
    while(lo+1<hi){
        int mid=(lo+hi)/2;
        if(check(mid)) hi=mid;
        else lo=mid;
    }
    printf("%d",lo+1);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/2343.cpp