코스모스 공작소

백준 2805 나무자르기 (성공) 본문

프로그래밍/알고리즘

백준 2805 나무자르기 (성공)

cosmos_studio_ 2020. 1. 20. 17:48
반응형

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

 

2805번: 나무 자르기

문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따

www.acmicpc.net

파라매트릭 서치 문제

랜선 자르기와 비슷한 문제

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
#include<iostream>
#include <algorithm>
 
using namespace std;
 
 
int main() {
    int K;
    cin >> K;
    int N;
    cin >> N;
 
    long long* list = new long long [K];
    for (int i = 0; i < K; i++)
    {
        scanf("%lld", &list[i]);
    }
 
    sort(list, list + K);
 
    long long start = 1;
    long long end = list[K-1];
    long long answer = 0;
    while (start <= end)
    {
        long long mid = (start + end) / 2;
        long long sum = 0;
        for (int i = 0; i < K; i++)
        {
            if (list[i] - mid >= 0)
            {
                sum += list[i] - mid;
            }
            
        }
 
        
        if (sum >= N)
        {
            start = mid + 1;
            if (mid > answer)
            {
                answer = mid;
            }
        }
        else
        {
            end = mid - 1;
        }
 
        
 
    }
    cout << answer;
 
    return 0;
}
cs
반응형

'프로그래밍 > 알고리즘' 카테고리의 다른 글

백준 1654 랜선 자르기 (성공)  (0) 2020.01.20
힙(heap) 과 힙정렬, 그리고 우선순위 큐  (0) 2019.12.18
백준 2468 안전영역 (bfs) [성공]  (0) 2019.12.18
백준 11047번 동전 0 [성공]  (0) 2019.12.08
백준 11399번 ATM [성공]  (0) 2019.12.06
'프로그래밍/알고리즘' Related Articles more
Comments