백준 1654번 c++ 풀이 (복습필요)

안녕하세요 오늘은 이분탐색, 매개변수 탐색 알고리즘을 이용하여 풀어야하는 문제를 풀어보겠습니다.

 

전략:

1. 벡터에 랜선의 길이를 대입하고 sort를 해줍니다. 이때 sort해서 가장 뒤에 있는 원소가 max 변수에 대입됩니다.

2. 매개변수로 l(left), r(right)를 선언해줍니다. l은 1, r은 max로 선언해줍니다. 

3. 갖고있는 랜선의 개수를 mid로 나눈 몫의 총합이 K보다 크거나 같으면 result와 sum을 비교해서 더 큰 값을 result에다가 대입해줍니다. 그리고, l = mid+1을 해줍니다.

4. 만약 아니라면  r = mid-1을 해준뒤, 만약 l>r이면 break하도록 if문을 설정해줍니다.

 

코드:

#include <bits/stdc++.h>
#include <vector>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, K;
	cin>>N>>K;
	vector<int> v(N);
	for(int i= 0; i<N; i++){
		int x;
		cin>>x;
		v[i] = x;
	}
	sort(v.begin(), v.end());
	int max = v[N-1];
	long long int l = 1, r = max;
	int result = 0;
	while(1){
		if(l>r){
			break;
		}
		int sum = 0;
		long long int mid = (l+ r)/2;
		for(int i= 0; i<N; i++){
			sum+=v[i]/mid; 
		}
		if(sum>=K){
			if(result< mid){
				result = mid;
			}
			l = mid+1;
		}
		else{
			r =mid-1;
		}
		
	}
	cout<<result;
}