[ 백준 C++ ] 2805번 나무자르기 ( 파라메트릭 서치 )

문제 

https://www.acmicpc.net/workbook/view/3492

문제집: 파라메트릭 서치(이분탐색(binary)/삼분탐색(ternary)) (daejjyu)

변수명을 start mid end 로 하는게 편할것같다. 

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) => 때문에 sum은 long long

4 7
20 15 10 17

 

start	end	mid	sum	sum    m	answer
0	20	10	10+5+2 =17	sum >= m	10
1511	20	15	5+2=7	sum == 7	15
16	20	18	2	sum < m	15
16	17	16	4+1 = 5	sum < m	15
17	17	17	3	sum < m	15
18	17				15
start > end 라서 while문 끝

 

 

 

코드

#include <iostream> 
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n,m; //n : 나무 수, m : 필요한 길이 
    vector<int> v;
    
    cin >> n >>m;
    for(int i=0; i<n; i++)
    {
        int tmp=0;
        cin >> tmp;
        v.push_back(tmp);
    }
    int start=0;
    int mid=0;
    int end = *max_element(v.begin(),v.end());
    long long int sum=0;
    int answer=0;
    while(start <= end)
    {
        mid = (start+end) /2;
        sum =0;
        for(int i=0; i<n; i++)
        {
            if(v[i]>mid)
                sum += v[i] -mid;
            
        }
        if(sum >= m)
        {
            answer = mid;
            start = mid +1;
        }else
        {
            end = mid-1;
        }
        
    }
    
    cout << answer;
    
    return 0;
    

    
}