[백준/C++] 알고리즘 2805번 - 나무 자르기

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 2805번 - 나무 자르기를 풀어보도록 하겠습니다.

 

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

2805번: 나무 자르기

 

[문제 접근]

시간 제한 1초, N은 100만이기 때문에 완전탐색이 불가능합니다.

적어도 M미터의 나무를 집에 가져가기 위해 절단기 설정할 수 있는 높이의 최댓값을 생각해보면

H를 점점 높여나가다가 어느 특정 지점을 넘어가는 순간 M미터 작아지는데 그 특정지점이 최댓값이라는 것을 알 수 있습니다.

여기서 최적화문제를 결정문제로 바꿔주는 파라메트릭 서치를 생각해볼 수 있습니다.

check라는 함수가 있을 때, check(lo) = true , check(hi) = false 입니다.

정답은 check(lo)값의 가장 큰 높이값을 요구하기 때문에 답은 lo에 있습니다.

 

[풀이 전략]

1. 오름차순 정렬을 합니다.

2. check 함수 만듭니다.

 - 모든 나무를 돌면서 나무높이가 인자로 들어온 높이보다 크면 차이만큼 sum변수에 더해줍니다.

 - sum >= m을 리턴합니다.

3. lo = 0, hi = max+1 = 1e9+1로 초기화합니다. ( lo +1 == hi, min ≤ target  = lo ≤ max를 고려해보면)

4. check함수가 true이면 lo = mid로, false면 hi = mid로 설정하여 lo+1 == hi 일때까지 반복합니다.

5. lo를 출력합니다.

 

[코드]

#include <iostream>
#include <algorithm>
using namespace std;

int n, m ;
int arr[1000001];

bool check(int mid) {
    long long sum = 0;
    for(int i = 0 ; i < n ; i++) {
        if(arr[i] > mid){
        sum += (arr[i] - mid);
        }
    }
    return sum >= m ;
}

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n >> m ; 
    for(int i = 0 ; i < n ; i++) cin >> arr[i];

    int lo = 0, hi = 1e9 ; 
    
    while(lo+1 <hi) {
        int mid = (lo + hi) / 2 ;
        if(check(mid)) lo = mid ;
        else hi = mid ;
    }
    cout <<lo ; 
}

 

[배울 점]

- 정답이 lo에 있는지, hi에 있는지 파악하고, 이에 맞추어 lo, hi를 초기화해주어야 합니다.

- lo + 1 == h 로 while조건을 걸어두어서 애초에 무한루프가 발생하지 않습니다.