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

문제 재정의 및 추상화

결론: 원하는 만큼의 나무를 가져가기 위해 나무를 베고 최대한 남길 수 있는 높이를 찾아라

문제 접근 방식

입력 수가 크지만 시간 제한은 1초이므로 선형 탐색은 시간 초과가 날 수 있다.

-> 이진 탐색을 써보자!

해법을 찾는데 결정적이었던 깨달음

📌 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 매우 크다!!(1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

long long 자료형을 써야한다!

문제 풀이 로직

1. 나무의 개수와 가져가고 싶은 나무의 길이를 입력받는다.
2. 나무의 개수만큼 반복하며 현재 있는 나무의 높이를 배열로 입력받는다.
3. 이진 탐색을 위해 나무 배열을 정렬하고 low값과 high 값을 초기화한다.
4. 자를 수 있을 때 까지 (low 값이 high 값보다 작거나 같을 때 까지) 아래를 반복한다.
   4-1. 자를 지점 cut을 low와 high의 중간으로 초기화한다.
   4-2. 나무 배열을 돌면서 자르고 남은 나무가 있다면 해당 나무 길이를 모두 합해준다.
   4-3. 자르고 남은 나무 길이의 합이 원래 가져가고자 했던 길이보다 많거나 같으면 현재의 cut 지점을 최대 지점으로 저장하고, low를 더 올린다.
   4-4. 자르고 남은 나무 길이의 합이 원래 가져가고자 했던 길이가 안되면 high를 더 내린다.
5. 위 과정을 반복하여 나온 최대 지점을 출력한다.

문제 풀이

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    long long n, m, max = 0;
    int tree[1000001];
    
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> tree[i];
    
    sort(tree, tree + n);
    
    long long low = 0;
    long long high = tree[n - 1];
    
    while(low <= high){ //cut 가능할 때 까지
        long long sum = 0;
        long long cut = (low + high) / 2;
        
        for(int i = 0; i < n; i++) {
            if(tree[i] - cut > 0) sum += tree[i] - cut; // cut 하고 남는 게 있다면 가져감
        }
        
        if(sum >= m){ // m미터보다 가져간 나무가 같거나 많으면
            max = cut; // 현재 cut 지점을 최대 지점으로 저장
            low = cut + 1; // cut 가능 구간을 더 올림
        } else{
            high = cut - 1; // m미터가 안 되면 cut 가능 구간을 내림
        }
    }
    
    cout << max; // 최대 cut 지점 출력
    
    return 0;
}