2805 나무 자르기

백준 2805 나무 자르기 https://www.acmicpc.net/problem/2805

1. Dynamic Programming $O(NlogN + N)$
정렬한 후에
$DP[N] = DP[N-1] + (tree[N-1]-tree[N])*N$의 값이 M이상일 경우에 정지시킨다.
$ans = (DP[N]-M)/N + tree[N]$ 

#include <cstdio> #include <algorithm> #include <functional> using namespace std; long long N, M; long long arr[1000002]; long long dp[1000002]; bool cmp(long long a, long long b){return a > b;} int main(){     long long ans;     scanf("%lld%lld", &N, &M);     for (int n = 0; n < N; n++)         scanf("%lld", &arr[n]);     sort(arr, arr + N, cmp);     dp[0] = arr[N] = 0;     for (long long n = 1; n <= N; n++){         dp[n] = dp[n - 1] + (arr[n - 1] - arr[n]) * n;         if (dp[n] >= M){             long long dif = dp[n] - M;             ans = (long long)(dif / n) + arr[n];             break;         }     }     printf("%lld\n", ans);     return 0; } Colored by Color Scripter

cs

2. Binary Search $O(logM)$

M을 이분탐색하며 값을 찾아준다.

#include <cstdio> long long N, M; long long arr[1000001]; bool cut(long long h){     long long sum = 0;     for (long long n = 0; n < N; n++){         if (arr[n] > h)             sum += arr[n] - h;     }     return sum >= M; } int main(){     long long ans = 0;     long long min = 0, max = 10000000000;     scanf("%lld%lld", &N, &M);     for (long long n = 0; n < N; n++)         scanf("%lld", &arr[n]);          while (min <= max){         long long middle = (min + max) / 2;         if (cut(middle)){             if (ans < middle)                 ans = middle;             min = middle + 1;         }         else             max = middle - 1;     }     printf("%lld\n", ans);     return 0; } Colored by Color Scripter

cs