2805번-나무자르기

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

2805번: 나무 자르기

---

접근방법

이 문제는 n이 1000000이므로 완전탐색처럼 모든 케이스의 경우를 탐색할 경우 시간초과가 발생한다.

적어도 O(logn)의 시간복잡도로 줄여줘야 하는 문제다.

문제에 따라 적어도 m개의 나무를 가지기 위한 기준값을 정해주어야 한다.

기준값은 left와 right를 이용해서 중간값을 정해주는데 left와 right의 정의는 나무의 최소길이부터 최대길이이다.

최소이므로 left = 0이고 right는 주어진 나무의 높이중 가장 큰것이다. (29번째 라인을 활용해 구해준다)

그 이후 37번째 라인부터 이분탐색을 시작한다.

내가 정한 기준값으로 m개의 나무를 취득하지 못했다면 right를 줄여서 m개의 나무를 더 많이 취득해줘야 한다.

(right가 줄 경우 기준값은 작아질 것이고 기준값이 작아지면 더 많은 나무를 취득할 수 있다.)

내가 정한 기준값으로 m개의 나무를 취득했다면 left크기를 올려서 기준값의 크기를 올려준다.

(left의 크기가 커질 경우 기준값은 커질 것이고 기준값이 커지면 더 적은 나무를 취득한다.)

이 때 마지막으로 갱신한 것이 m개의 나무를 취득할 수 있는 가장 큰 기준값이다.

---

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 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include<bits/stdc++.h> #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define pii pair<int,int> #define mp(X,Y) make_pair(X,Y) #define mt(X,Y) make_tuple(X,Y) #define mtt(X,Y,Z) make_tuple(X,Y,Z) #define ll long long #define sz(v) (int)(v).size()   using namespace std; const int MAX = 1e6 +1; int n,m; ll arr[MAX];   int main(void) {     fastio;     cin >> n >> m;       ll maxValue = INT_MIN;     for(int i = 0; i < n; i++)     {         cin >> arr[i];         maxValue = max(maxValue, arr[i]);     }       ll left = 0;     ll right = maxValue;     ll ans = 0;       while(left <= right)     {         ll mid = (left + right) / 2;           ll sum = 0;         for(int i = 0; i < n; i++)             if(arr[i] > mid)              sum += arr[i] - mid;           if(m <= sum)         {             left = mid + 1;             ans =  mid;         }         else if(m > sum)         {             right = mid - 1;         }     }     cout << ans <<"\n"; }     Colored by Color Scripter

cs