[백준] 랜선자르기 (1654 / C++)

문제

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

1654번: 랜선 자르기

 

풀이

이분 탐색을 바로 생각해내야만 하는 문제였다. 이분 탐색 기본 유형

조건을 만족하면서(Possible) 조건 내 최댓값을 이분 탐색을 통해 찾아내야 한다.

 

이분 탐색시 랜선길이 개수를 보면 2^32-1 이다. 이를 전부 탐색하려면 이분탐색 방법뿐만 아니라 자료형 또한

long long 이 필요함을 잊지 말자. 

 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int N; //필요한 랜선 개수
int K; //보유한 랜선 개수
vector<long long> kk; //랜선길이개수가 2^32-1 보다 작거나 같은 자연수이므로 longlong 선언
bool Possible(int mid) {
	long long cnt = 0;
	for (int i = 0; i < K; i++) {

		cnt += kk[i] / mid;

	}
	if (cnt >= N) {
    
		return true;
	}
	return false;

}
int main() {
	cin >> K >> N;
	//항상 K <= N

	for (int i = 0; i < K; i++) {
		int a; 
		cin >> a;
		kk.push_back(a);
	}

	//이분탐색
	long long low = 1;
	long long result = 0;
	//high찾기
	long long high = 0;
	for (int i = 0; i < K; i++) {
		
		high = max(kk[i], high);

	}

	while (low <= high) {
		long long mid = (high + low) / 2;
		if (Possible(mid)) {

			if (result < mid)  result = mid;

			low = mid + 1;
		
		}
		else {
			high = mid - 1;
		}

	}

	cout << result;

	return 0; 
}