[C++] 백준 2805 : 나무 자르기

문제

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

 

 

풀이

  이분 탐색으로 최대 길이를 찾는다. 만약 이분 탐색이 아닌 완전 탐색을 이용할 경우, 시간 초과가 발생한다.

  또 자료형으로 long long을 사용해야 모든 테스트케이스를 통과할 수 있다.

  자세한 구현 방식은 아래의 코드 주석을 참고하면 된다!

 

코드

#include <iostream>
using namespace std;

long long n,m, maximum=0, r;
long long arr[1000000];

// 테케1 예시
// 0~20 -> 10 --> 충분(r=10) / 10~20 에서 15 --> 충분(r=15) / 15~20 에서 17 부족(r=15)
// 15~17 에서 16 부족(r=15) / 15~16 에서 15는 기존 충분 높이와 동일(r=15) => 종료

// 현재 길이로 자를 수 있는 나무 계산
long long cal(int h){
    long long ans=0;
    for(int i=0; i<n; i++){
        int d = arr[i] - h; // 현재 높이로 자를 수 있는 나무의 길이
        if(d >0) ans+=d;  // 나무의 길이가 음수라면 실제로는 자르지 못한 것이므로 제외하고 더함.
        if(ans >=m) break; // 만약 나무 길이의 합이 이미 m을 넘었다면, 더 계산할 필요 없음.
    }
    return ans;
}

int main()
{
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> arr[i];
        if(arr[i] > maximum) maximum = arr[i]; // 입력받으면서 나무의 최대 길이 저장
    }
    
    long long left = 0, right = maximum;
    
    // 이분 탐색
    while(left <= right){
        long long mid = (left + right)/2; // 중간값 계산
        long long ans = cal(mid); // mid를 높이로 할 때의 얻을 수 있는 나무 길이 합 계산
        
        // 만약 목표 길이를 채웠다면, left=mid로 설정해 다음에 계산할 높이를 증가(최대 높이를 구해야 함)
        if(ans >= m){
            left = mid;
            
            // 만약 기존에 구했던 높이와 동일하다면, while문 종료(무한 루프 탈출)
            if(mid == r) break;
            
            // 기존 높이보다 더 큰 높이를 구한 경우, 높이의 최댓값 r 갱신
            if(mid > r) r = mid;
        }
        
        // 만약 목표 길이에 모자라다면, 높이를 줄여야 함. right = mid
        else{
            right = mid;
        }
    }
    
    cout << r << "\n";
    
    return 0;
}