[BOJ/C++] 13397: 구간 나누기2

🏅 Gold 4

✏️ 최종 솔루션

⭐️ 이분 탐색 풀이
⭐️ 구간 점수의 최댓값을 이분 탐색

1. left = 0, right = 입력 받은 숫자 중 최대값
2. 구간을 분할하지 못한다면 구간은 총 1개이므로 구간 count 는 1로 초기화
3. mid 를 모든 구간점수 중에 최대값으로 정의했기 때문에 입력받은 숫자를 돌면서 구간 점수가 mid 보다 커지는 시점에서 구간 분할
   1) 매 숫자마다 최소값과 최대값을 갱신
   2) 현재 숫자에서 구간 점수가 mid 보다 커지면 구간 count
   3) 현재 숫자부터 새로운 구간에 포함되는 것이므로 최대값과 최소값을 현재 숫자로 초기화
4. 현재 mid 값이 구간 중 최대값일 때 총 구간 개수가 m 개 이하이면 구간점수를 최소값으로 정답에 갱신하고 right = mid - 1 으로 구간점수의 범위를 mid 이전으로 설정
5. 구간 개수가 m 개보다 많으면 구간 점수를 최대값으로 정답에 갱신하고 left = mid + 1 으로 구간점수의 범위를 mid 이후로 설정

📌 self feedback

• 구간 점수의 값을 이분탐색 범위로 설정해야한다는 것까지는 파악했으나 구간 점수의 최대값과 최소값 중 어느 것을 구간점수로 해야할지 파악하지 못함
• 최종적으로 구간 중의 최대 구간점수를 낮추는 것이 목표이기 때문에 구간 점수의 최대값을 이분탐색 범위로 설정하고 mid 를 조정하면서 최소값을 탐색해야했음

✏️ 최종 code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n,m;
    
    cin>>n>>m;
    
    vector<int> v(n);
    int mx=0;
    for(int i=0;i<n;i++) {
        cin >> v[i];
        mx=max(mx,v[i]);
    }
    
    int left=0,right=mx,ans=100001;
    while(left<=right) {
        int mid=(left+right)/2;
        
        int mn=v[0],cnt=1;
        mx=v[0];
        for(int i=1;i<n;i++) {

            mn=min(mn,v[i]);
            mx=max(mx,v[i]);
            
            // 구간 점수가 mid 보다 크면 구간 count -> 현재 인덱스부터 새로운 구간 시작하는 것
            if(mx-mn>mid) { 
                cnt++;
                
                // 현재 구간부터 새로운 구간 시작하기 때문에 최대, 최소값 초기화
                mn=v[i];
                mx=v[i];
            }
        }

        if(cnt<=m) {
            ans=min(ans,mid);   // 구간점수 최소값으로 갱신
            right=mid-1;
        }
        else left=mid+1;
    }

    cout << ans << endl;
}