[ BOJ 백준 2343번 - 기타 레슨 ] 해설 및 코드

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

 

목적

M개의 블루레이에, N개의 레슨 동영상을 블루레이 크기를 초과하지 않는 만큼 순서대로 채워 넣을 때, 가능한 블루레이의 최소 크기를 구하자.

 

접근법

1. 부분합과 이분탐색 알고리즘을 이용하여 접근한다. (이분 탐색 과정 참고 : 백준 2110 - 공유기 설치)

2. 블루레이의 크기를 정했다면, N 개의 레슨 동영상을 M개의 블루레이에 담을 수 있는지 여부를 확인해야한다.

#include<iostream>
using namespace std;
 
int n,m,a[(int)1e5+1]={0};
 
bool valid(int k){
    int i=0,j,cnt=m;
    while(i<n){
        j=i+1;
        if(cnt<1||a[j]-a[i]>k)return false;
        while((++j)<=n&&a[j]-a[i]<=k);
        --cnt;
        i=j-1;
    }
    return true;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        a[i]+=a[i-1];
    }
    
    int l=1,r=1e9;
    while(l<=r){
        int mid=(l+r)/2;
        if(valid(mid))r=mid-1;
        else l=mid+1;
    }
    cout<<l;
}
 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.