[C++] 백준 1654. 랜선 자르기

🌽 문제

🥕 입출력

🥔 풀이

자를 수 있는 길이 범위를 1부터 가장 긴 랜선 길이로 두고 이분 탐색을 진행한다.

수의 범위가 크기 때문에 오버플로우 방지를 위해 long long을 사용했다.
오버플로우는 중간값인 m 계산 시-(1 + (2^31-1)) / 2-발생할 수 있고,
m이 최댓값일 때 l 갱신 시-l = (2^31-1) + 1-발생할 수 있다.
참고로 int의 범위는 -2^31 ~ 2^31 - 1이다.

len을 갱신할 때 max(len, m)를 사용할 수도 있지만
len과 m의 자료형이 다르므로 len의 자료형을 바꾸는 대신
조건문으로 미리 걸러주는 방식을 사용했다.

🥬 코드

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

int K, N;
int len = 0;
vector<int> v;

void solution() {
	long long l = 1;
	long long r = v[K - 1];
	long long m, cnt;
	while (l <= r) {
		m = (l + r) / 2;
		cnt = 0;
		for (int i = 0; i < K; i++)
			cnt += v[i] / m;
		if (cnt < N)
			r = m - 1;
		else if (cnt >= N && m > len) {
			l = m + 1;
			len = m;
		}
	}
	return;
}

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

	cin >> K >> N;
	v.resize(K);
	for (int i = 0; i < K; i++)
		cin >> v[i];
	sort(v.begin(), v.end());

	solution();
	cout << len;
	
	return 0;
}

🥜 채점

이분탐색이라고 떠먹여줘도 몰루기,, 발전 언제 할건데