[백준 2805] 나무 자르기

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

예전에 class3 에센셜 문제를 다 풀었었는데, 새롭게 한 문제가 생겼길래 풀어봤다.
제일 까다로웠던 부분이 나무의 길이가 '넘침'>'적음'>'넘침'으로 갈 때 종료 조건을 어떻게 할까였는데, 생각하다가 max-min>1일때(예를 들어 13~15면 middle이 14로 고정이므로)로 설정했다.

• 참고로 다른 사람들은 (min < max)로 값이 엇갈리는지 확인하는 방식도 사용했다. 왜 나는 문제 풀면서 이리 쉬운 생각을 못했을까.. 이진 탐색 연습이 많이 필요해보인다.

풀이 과정

1. 나무의 최댓값을 찾는다.
2. 최댓값과 최솟값의 중간 값 만큼 나무를 자른다.
3. 자른 나무가 m보다 크다면 min을 middle로 바꾼다.
4. 자른 나무가 m보다 작으면 max를 middle로 바꾼다.
5. max-min이 1보다 작거나 같을때까지 반복한다.
   • max-min이 1이 되면 middle이 정해지기 때문에 더 할 필요가 없다.

시간 복잡도

이진탐색($logm$) * 나무의 개수($n$)
= $O(nlogm)$

구현

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n;
    long long m;
    int arr[1000000];
    
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    int min=0,max=*max_element(arr, arr + n);// 최대 나무 길이 찾기
    while (max-min>1) // 중간 값이 고정 됨
    {  
        int middle = (min+max)/2;
        long long cnt=0;
        for(int i=0; i<=n-1; i++){ // 나무 길이 합하기
            if(arr[i]-middle>0) cnt+= arr[i]-middle;
        }
        if(cnt == m) break;
        else if (cnt > m){ // m보다 합이 크면 >> 더 조금 잘라야 함
            min = middle;
        }
        else { //m 보다 합이 작으면 >> 더 많이 잘라야 함
            max = middle;
        }
    }
    cout<<(min+max)/2; 
    
    return 0;
}