기타 레슨 C++ - 백준 2343

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

파라메트릭 서치 문제.

이 문제를 풀면서 파라메트릭 서치의 답을 도출할때 무엇을 선택해야 할지

다시 생각하게 된 문제이다. (s,mid,e 중 하나)

풀이

블루 레이의 값을 이분탐색해준다. (s는 강의 중 최댓값, e는 강의들의 합)

강의가 블루레이에 들어가야하기 때문에 s를 강의 중 최댓값으로,

최소 블루레이 개수가 1개 이므로 e를 강의들의 합으로 정했다.

cnt를 활용해 mid보다 값이 커지면 cnt++을 해주고,

cnt와 m을 비교해 s,e를 조정해주었다.

이 문제는 여태까지 했던 파라메트릭 서치 문제들과는 다르게 max값이 아닌

min값을 구하는 문제였다.

while문의 종료조건은 s가 e보다 클 때이다.

s가 e보다 커지는 경우는

1. cnt=m -> e=mid-1 (s=e여서 e가 s보다 작아짐)
2. cnt<m -> s=mid+1 (s=e여서 s가 e보다 커짐)

첫번째는 e가 범위 밖을 이동하므로 조건을 만족하는 s가 답이고,

두번째는 처음에는 조건을 만족하지 않았지만 s가 조정되어 답이된 경우여서

s가 답이다. 따라서 s를 출력하면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int lect[100000];
int n,m;
int mini=0;
int maxi=0;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m;
    for(int i=0;i<n;i++){
        cin >> lect[i];
        maxi+=lect[i];
        mini=max(mini,lect[i]);
    }
    int s=mini;
    int e=maxi;
    while(s<=e){
        int mid=(s+e)/2;
        int sum=0;
        int cnt=0;
        for(int i=0;i<n;i++){
            if(sum+lect[i]>mid){
                cnt++;
                sum=lect[i];
            }
            else{
                sum+=lect[i];
            }
        }
        if(sum>0) cnt++;
        if(cnt>m){
            s=mid+1;
        }
        else{
            e=mid-1;
        }
    }
    cout << s;
}