[BOJ/C++]2805번_나무자르기

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

##문제 풀기 전 알아야 할 개념 :

1_ " 1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000" : 입력된 수의 범위를 보고 2가지를 떠올려야 한다.

• long long 의 자료형으로 변수 초기화 , (또는 unsigned int)
• 저렇게 범위가 많다는 것 => log(N)의 시간 복잡도 알고리즘을 사용할 것이라는 습관을 들여야 한다.

2_ 0 ~ 입력된 나무의 높이의 범위 사이에서 적절한 높이를 탐색(최적화 문제) 해야한다. => 이분탐색(or 이진 탐색)

##문제 풀이의 논리 노트 :

1_ 나무의 높이들 입력하면서, 최대 높이를 업데이트

2_ 최대 높이부터 내리면서(순차 탐색 x , 이진 탐색 o), 문제 조건에 맞는지 검사하기

• ★ " 0 ~ 최대 나무 높이 "가 이분탐색의 Scan의 대상이다.
• 절단기 설정 높이이에 대한 누적 잉여 나무 높이 >= 상근이가 필요한 최소 높이(M)

ex_ < 예제 입력 2> 분석해보기

 

##코드 :

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void init() {
 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
 
 
int main() {
 
    init();
 
    long long N, M, max=0;
    long long ans = 0;
    cin >> N >> M;
 
    vector<long long> Tree(N);
    //입력과 최대 나무 길이 추출
    for (int i = 0; i < N; i++) {
        cin >> Tree[i];
        if (max < Tree[i]) {
            max = Tree[i];
        }
    }
 
    //이분탐색으로 적절한 높이 찾기
    unsigned int start = 0;
    unsigned int end = max;
 
    while (start<=end) {
        unsigned int mid = (start + end) / 2;
        unsigned int taken = 0;
        //mid 높이가 적절한 높이가 되는지 check하기
        //1_ Tree들 순회
        for (int i = 0; i < N; i++) {
            if (Tree[i] >= mid) {
                taken += Tree[i] - mid;
            }
 
            if (taken >= M) {
                break;
            }
        }
 
        //2_ 높이의 범위 줄이기
 
        if (taken >= M) {
            ans = mid;
            start = mid + 1;
        }
        else if (taken < M) {
            end = mid - 1;
        }
    
    }
 
    cout << ans << '\n';
 
 
    return 0;
}