문제링크

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

사용 알고리즘

  º  이분탐색

 

시간복잡도

  º  $\mathcal{O}(Nlog(10^{10}))$

 

풀이

 

N개의 나무들이 주어질때 상근이가 나무를 M미터 챙겨서 가려고 합니다. 나무를 절단하는 높이가 H라고 할때 H보다 높은 부분 즉 나무의 높이 - H만큼의 길이가 한 나무에서 자르는 나무의 길이일때 이걸 합쳐서 M미터를 만들어주면 됩니다.

문제해결을 위해선 H의 높이를 계속해서 주어진 입력값에 대해 적용하여 잘라줘야하는데 나무의 높이로 주어질 수 있는 최대값이 10억입니다. 그래서 이분탐색으로 자를 나무의 높이를 탐색합니다. 최대 $\mathcal{O}(log(10^{10}))$ = 10d의 시간소모.

 탐색을 진행하며 동시에 나무를 잘라서 M미터가 되는지 검사해주는데 지금 자르는 높이보다 작은 나무는 자른 높이를 더해주면 안됩니다. (당연한 얘기같지만 저는 그래서 답이 다르게 나오길래 뭐지했습니다.) 어찌됐든 그래서 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
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int n;
    long long m,max_t=0;
    vector <long long> v;
    cin >> n >> m;
    v.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        if (v[i] > max_t)
            max_t = v[i]; // 가장 큰 키의 나무를 찾아준다.
    }
    long long mid,left = 0, right = max_t, result, ans = 0;
    while (left <= right)
    {
        mid = (left + right) / 2;
        result = 0;
        for (int i = 0; i < n; i++)
        {
            if(mid <v[i]) // 자르는 길이보다 나무가 클때만 잘라준다.
                result += (v[i] - mid);
        }
        if (result >= m)
        {
            left = mid + 1;
            if (mid > ans)
                ans = mid;
        }
        else
            right = mid - 1;
    }
    cout << ans;
    return 0;
}
Colored by Color Scripter
cs

'Algorithm > boj' 카테고리의 다른 글

백준 13397번 구간 나누기 2  (0) 2021.10.24
백준 1939번 중량제한  (0) 2021.10.24
백준 2110번 공유기 설치  (1) 2021.10.24
백준 14890번 경사로  (0) 2019.11.11
백준 14503 로봇 청소기  (0) 2019.11.11

+ Recent posts