언제나 처음처럼

[문제 링크]

https://onlytrying.tistory.com/54

나무 자르기 문제와 비슷한 유형의 문제였다.

랜선을 자르는 길이가 길어질수록 만들어지는 랜선의 갯수는 무조건 작아지기 때문에 자르는 길이와 만들어지는 랜선의 갯수는 서로 반비례한다는 것을 알 수 있다.

알고리즘은 나무 자르기 문제와 동일하다.

차이점으로는 0cm 길이의 랜선을 가져갈 수는 없기 때문에 start의 초기값을 0이 아닌 1로 해야 하고, 입력되는 정수의 최댓값이 크므로 unsigned int나 long long 자료형을 사용해야 한다.

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

int main(void)
{
	int K, N;
	cin >> K >> N;
	
	vector<int> utp(K);
	for (int i = 0; i < K; i++)
		cin >> utp[i];
	
	sort(utp.begin(), utp.end());
	
	long long start = 1, end = utp[K - 1];
	int result;

	while (start <= end)
	{
		long long mid = (start + end) / 2;
		int sum = 0;

		for (int i = 0; i < K; i++)
			sum += utp[i] / mid;

		if (sum >= N)
		{
			result = mid;
			start = mid + 1;
		}
		else
			end = mid - 1;
	}
	cout << result << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 46 day