[2805번] 나무 자르기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이진 탐색 응용

이 문제는 DP라고 생각이 처음 들 수 있겠지만, 자세히 확인해보면 이진 탐색으로 빠르게 해결 할 수 있다.

하지만 이진 탐색 코드를 그대로 쓰면 안되고, 조금 응용해서 써야한다.

소스코드에 대한 설명은 주석을 통해 자세히 달아두었다.

소스 코드 : 

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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

#include <iostream> #include <cstring> #include <algorithm>   using namespace std;   int tree[1000001];   int binarysearch(int n, int target) {     int first = 0;     int last = tree[0];     int mid = 0;       long long int ans = 0;       while (first <= last)     {         // first :: 가장 낮은 나무의 높이, 처음은 0으로 잡는다.         // last :: 가장 높은 나무의 높이, 정렬한 상태이니 tree[0]가 가장 높다.         // mid의 의미 :: 가장 높은 나무와 낮은 나무의 / 2한 값         // 이것을 이용하여 잘랐을 때의 길이의 합을 가져올 수 있다.             mid = (first + last) / 2;           // 전체 나무의 길이를 더한다.         for (int i = 0; i < n; i++)             ans += tree[i];           // mid보다 아래 나무 즉, 잘리지 않은 나무의 길이는 빼줌으로써         // ans변수에 벌목했을때의 나무 길이를 가져올 수 있다.         for (int i = 0; i < n; i++)         {             if (tree[i] >= mid)                 ans -= mid;             else                 ans -= tree[i];         }           if (target == ans) // 정답이 타겟과 같다면             return mid; // 탐색 완료           else // 타겟이 아니라면 탐색 대상을 반으로 줄인다.         {             if (target < ans)                 first = mid + 1;               else                 last = mid - 1;         }           ans = 0;       }       // 만약 이진 탐색에서 탐색을 실패할 시,     // mid를 마지막으로 구해주고 리턴해준다.     mid = (first + last) / 2;     return mid; }   bool comp(const int &a, const int &b) {     return a > b; }   int main() {     int n, want;       scanf("%d %d", &n, &want);       for (int i = 0; i < n; i++)         scanf("%d", &tree[i]);       // 나무를 내림차순으로 정렬해준다.(가장 큰 나무를 잡아내기 위해)     sort(tree, tree + n, comp);       // 나무 개수, 원하는 벌목 길이     cout << binarysearch(n, want);         return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus