[C++] 백준 2805 - 나무자르기(이분 탐색, 이진 탐색, binary search)

0. [c++] 백준  -

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

1. 풀이

문제에 처음 접근할 때, 자르는 경우마다 전체를 탐색하며 자른 나무의 총 합을 탐색하면 시간초과가 발생할 것이라 예상했는데, 막상 그렇지 않다는 것을 알았다.

문제 풀이는 이진 탐색의 방색으로 진행된다.

low, high를 활용하고, 중간값을 계속 구하며 탐색이 진행된다.

높이에 포인트를 두고 높이가 변경된 경우 for문을 통해 자른 길이의 합이 M을 넘은지 지속적으로 확인하며 최대 높이를 구하면 되는 문제였다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include<iostream> #include<algorithm>   using namespace std;   int arr[1000001];   int N, MAX=0, M;   int main() {     cin.tie(0);     cin.sync_with_stdio(0);     int low = 0, mid, high = 0, ret = 0;     long long sum;       cin >> N >> M;     for (int i = 0;i < N;i++) {         cin >> arr[i];         if (high < arr[i])             high = arr[i];     }       while (low <= high) {         mid = (high + low) / 2;         sum = 0;         for (int i = 0;i < N;i++)             if (arr[i] - mid > 0)                 sum += arr[i] - mid;         if (sum >= M) {             if (ret < mid)                 ret = mid;             low = mid + 1;         }         else             high = mid - 1;     }       cout << ret; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!