[백준 1654] 랜선 자르기

우선 특정 범위 내 특정 값을 찾는 것이므로 이분탐색으로 풀어야하는 것임을 알 수 있다

 

경계값 상황에 대해 정확하게 생각하지 못해서 틀리고 2주간 방치해두었다가 다시 풀었다

 

우선 최대값이므로 N만큼 나온다고 끝내면 안되고 N과 N-1개가 나오는 경계를 찾아야한다

그래서 start<=end 만큼 돌려준다

 

근데  여기서 놓친게 두 가지가 있다

 

1. cnt 뿐만 아니라 mid도 long long이 될 수 있다는 것

 

2. 경계값에서 나올 수 있는 상황 두 가지

 

---

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

using namespace std;

vector<int> v;
int N;

long long func(long long len) {
	long long cnt = 0;
	for (int i = 0; i < v.size(); i++) cnt += v[i] / len;
	return cnt;
}

long long binary_search(long long start, long long end) {
	long long mid;
	long long cnt;
	long long ans;

	// 특정 값을 찾는것이 목적이 아니라 최대값을 찾는 것이기 때문에
	// 원소 1개 남을때까지 돌아야함
	// 경계값 찾기
	while (start <= end) {
		mid = (start + end) / 2;
		cnt = func(mid);
        
		// 개수가 더 많거나 같게 나오면 랜선을 더 길게해보기
		if (cnt >= N) {
			start = mid + 1;
			ans = mid; 
		}
		else if (cnt < N) end = mid - 1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int K, x; cin >> K >> N;

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

	sort(v.begin(), v.end());
	cout << binary_search(1, v.back());

	return 0;
}