zz12345의 코딩 공부

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

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

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
#include <iostream>
using namespace std;
 
int main() {
    int n;
    long long m,mid,min=0,max=0,ans=0;
    cin>>n>>m;
    long long arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        if(max<arr[i]) max=arr[i];
    }
    
    max--;
    while(min<=max)
    {
        mid=(min+max)/2;
        long long sum=0;
        for(int i=0;i<n;i++)
        {
            sum+=(arr[i]-mid)>=0?arr[i]-mid:0
        }
        if(sum<m) max=mid-1;
        else
        {
            if(ans<mid) ans=mid;
            min=mid+1;
        }
    }
    cout<<ans;
    return 0;
}
cs

 

 

풀이

백준 1654번과 유사한문제이다.

https://zz12345.tistory.com/15

 

백준 1654번 : 랜선 자르기 (C++) (이분탐색)

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000..

zz12345.tistory.com

 나무를 가장 낮은 높이에서 자를 경우는 0이고 높은 높이에서 자를 경우는 가장 높은 나무의 높이-1이다. 1부터 가장 높은 나무의 높이-1까지를 모두 검사해서 답을 찾는 방법은 시간제한이 초과할 것이라고 생각해서 이분 탐색을 사용했다. 이분 탐색을 수행할 때 각 나무의 높이 - mid 값을 전부 더하여 가져가려는 나무의 높이와 비교하는데 각 나무의 높이 - mid가 마이너스가 된다면 (나무보다 높은 곳에 절단기를 둔다면) 가져가는 나무는 0이 되기 때문에 22행에 삼항연산자를 사용해서 마이너스 값이라면 0으로 바꿔줬다. 각 나무의 높이-mid 값을 전부 더한 값이 가져가려는 높이보다 작다면 max=mid -1을 해주어서 나무를 더 낮은 높이에서 자른다. 나무를 잘랐을 때 가져가려는 나무 높이보다 큰 값이 나온다면 그럴 때 가장 큰 mid 값을 저장하기 위해 27행을 수행하고 더 높게 잘라도 가져가려는 나무보다 큰 값이 나오는지 알아보기 위해 28행에서 min=mid+1을 수행해준다. 이를 min<=max가 true일 때까지 수행한 뒤 ans의 값이 답이다.

공유하기

facebook twitter kakaoTalk kakaostory naver band