백준 2805번: 나무 자르기

문제 링크 : https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 문제 설명 

 

1.나무의 갯수와 필요한 나무의 길이를 입력받고 다음줄에 나무의 높이 가 주어진다.

2. 톱질로 나무를 자를때 똑같은 위치에서 잘라야한다.

3. 그때 몇 m 에서 톱질해야 필요한 나무이상을 가져갈수있을까 ?  이때의 나무 높이의 최대 값 출력

 

 알고리즘 

 

이분탐색을 이용하여 나무 높이를 구해주었다.

 

반잘라서 나오는 높이가 목표보다 크거나 같다-> low를 mid 로

목표보다 작다-> hi를 mid 로

 

1. lo= 0 , hi = 20 , mid = 10 ,sum = 22 >= M(7) -> lo=mid+1
2. lo= 10 , hi = 20 , mid = 15 ,sum = 7 >= M(7) -> lo=mid
3. lo= 15 , hi = 20 , mid = 17 ,sum = 3 < M(7) -> hi=mid

4. lo= 15 , hi = 17 , mid = 16 ,sum = 5 < M(7) -> hi=mid

lo(15) 출력

 

 코드 

#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
 
ll N, M;
int arr[1000000];
 
int main() {
    int max_num = -1;
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        cin >> arr[i];
        max_num = max(max_num, arr[i]);
    }
 
    //hi는 max_num 으로 시작.
    int lo = 0, hi = max_num;
    // 이분 탐색 시작
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
 
        long long sum = 0;
        for (int i = 0; i < N; i++)
            if (arr[i] > mid) sum += arr[i] - mid;
 
 
        
        if (sum >= M) lo = mid;
 
        else hi = mid;
    }
    cout << lo;
    
 
}

다른 문제는 보통 lo = mid+1 ,hi = mid-1 로 지정했는데 이문제만좀 특이(?) 해서 오래 걸렸다 ,,