[백준 2805] 나무 자르기

문제

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

2805번: 나무 자르기

 

 

문제 분석 

상근이가 필요한 나무의 조각의 크기와 나무조각들이 주어지고 나무조각을 얼만큼 남기고 짤라야하는지 구하는 문제이다. 

 

다만 최대한 많이 남기고 잘라야한다. 

 

 

알고리즘 설계

long long을 가진 vector tree를 선언한다. 

또 long long n과 m, input을 선언한다. n은 나무의 개수, m은 얻어야하는 나무의 크기, 나무들을 입력 받을 변수이다. 

 

n과 m을 각각 입력 받고, n만큼 반복문을 돌린다. 

반복문에서 input에 입력 받고, tree에 push_back을 사용하여 값을 넣어준다. 

 

이후 sort을 하여 정렬해주고, 'binarySearch'라는 함수를 만들어  m과 함께 넘겨준다. 

 

'binarySearch'에선 left, right, cutting, sum을 선언한다. left는 1, right는 tree의 back값을 넣어준다. 

 

left가 right와 같거나 작을때 실행되는 while을 만들어주고, 

그 while 안에서 cutting을 left와 right을 더한 값에 0.5을 곱한 값을 넣어주고, sum을 0으로 초기화한다. 

tree를 범위기반 for문을 돌리고, 나온 값을 k라고 한다. k가 cutting보다 크다면 sum에 k에 cutting을 뺸 값을 더해주고 범위기반 for을 끝낸다. 

만약 sum이 m보다 크거나 같으면 left을 cutting + 1값으로, 

아니라면 right을 cutting - 1값으로 해주고 while을 끝낸다. 

 

이후 right을 반환하고, 그 값을 출력한다. 

 

 

유의점

매개변수 탐색에대한 이해가 필요하다. 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long>tree;

long long binarySearch(long long n, long long m);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n, m, input;

    cin >> n >> m;
    while (n--)
    {
        cin >> input;
        tree.push_back(input);
    }

    sort(tree.begin(), tree.end());
    cout << binarySearch(tree.back(), m);
}

long long binarySearch(long long n, long long m)
{
    long long left = 1, right = n, cutting, sum;
    while (left <= right)
    {
        cutting = (left + right) / 2;
        sum = 0;
        for (long long k : tree)
        {
            if (k > cutting)
                sum += k - cutting;
        }

        if (sum >= m)
            left = cutting + 1;
        else 
            right = cutting - 1;
    }
    return right;
}