랜선 자르기 #1654 c++ 풀이

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

 

처음 생각한것 : 순회 

2억번 이상 연산으로, 시간 초과가 날 가능성이 있어보여서 순회가 아닌 다른 방식을 사용해야한다.

랜선을 자를 수 있는 경우가 1~들어온 랜선의 최대길이 이므로, sorting되어진 리스트의 이진 탐색을 사용하여, 구현해야하는 문제이다.

또한 자료형도 생각해봐야한다. 정수 끝까지 2^31-1 값이 들어갈 수 있으므로,

unsigned int를 사용해주는 것이 좋다. 

 

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

unsigned int list[10000];
int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int K, N;

	cin >> K >> N;
	unsigned int m = 0;
	unsigned int answer = 0; 
	for (int i = 0; i < K; i++) {
		cin >> list[i];
		m = max(m, list[i]);

	}
	unsigned int left = 1;
	unsigned int right = m;
	unsigned int mid;

	while (left <= right) {
		mid = (left + right) / 2;
		unsigned int sum = 0;
		for (int i = 0; i < K; i++) {
			sum += list[i] / mid;
		}
		if (sum >= N) {
			left = mid + 1;
			answer = max(answer, mid);
		}
		else {
			right = mid - 1;
		}
	}
	cout << answer << '\n';
	


	return 0;
}