백준 2805번 c++ 풀이

안녕하세요 오늘은 이분탐색을 이용한 문제를 풀어볼 것입니다.

 

전략:

1. long long int type으로 vector를 선언해줍주고 입력을 받는다.

2. l(low)를 1로, h(high)를 vector의 최댓값으로 선언해주고, while문을 만든다.

3. while문이 시작되자마자 l가 h보다 크면 while문이 끝나도록 코드를 짜고, long long int타입의 mid라는 변수를 들어서 l, h의 평균을 입력해준다.

4. 나무를 자른 길이를 cnt에 더해주고, cnt가 M보다 크면  max변수와 mid를 비교하여 더 큰 값을 max에 넣어준다.

 

코드:

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin>>N>>M;
	vector<long long int> v(N);

	for(int i = 0; i<N; i++){
		long long int x;
		cin>>x;
		v[i] = x;
	}
	sort(v.begin(), v.end());
	long long int mid, max = 0, l = 1, h = v[N-1];
	while(1){
		if(l>h){
			break;
		}
		mid = (l+h)/2;
		long long int cnt = 0;
		for(int i= 0; i<N; i++){
			if(v[i]-mid>0){
				cnt += v[i]-mid;
			}
		}
		if(cnt>=M){
			if(max<mid){
				max = mid;
			}
			l = mid+1;
		}
		else{
			h =  mid-1;
		}
		
	}
	cout<<max<<"\n";
}