[백준/Baekjoon] 2805 나무 자르기 C++ :: Binary Search

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

2805번: 나무 자르기

---

1. Logic

스탠다드한 이분탐색 문제이다. 주의할 점은 문제에서 포커스를 맞춰야 할 곳이 절단기에 설정할 높이를 구하는 것이고, 절단기에 설정한 높이를 나무의 길이에서 빼준 값으로 비교해야 한다는 점이다.

 

이분탐색이 이해가 잘 안간다면 아래의 알고리즘 설명글을 참고하면 좋을 것 같다!

https://go2gym365.tistory.com/87

[Algorithm] 이분탐색 / Binary Search

 

 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m;
long long ans = LLONG_MAX;

vector<int> input;

long long calc(int mid) {
    long long sum = 0;
    for(int i = 0; i < n; i++) {
        if(input[i] > mid)
            sum += input[i] - mid;
    }
    return sum;
}

long long binarySearch() {
    int low = 0;
    int high = input[n - 1];
    int mid;

    while(low <= high) {
        mid = (low + high) / 2;

        long long temp = calc(mid);

        if(temp >= m) {
            low = mid+1;
        }
        else {
            high = mid-1;
        }
    }

    return high;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        input.push_back(a);
    }

    sort(input.begin(), input.end());

    cout << binarySearch();
}

 

 

---

3. Feedback

이분탐색이 어떻게 돌아가는지는 이해갔는데 그 안에서 low값과 high값을 출력하는 부분에 대해 헷갈리는 부분이 생겼다. 이부분에 대해 다시 살펴봐야겠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90