[Silver 2] 1654번 랜선 자르기

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

1654번: 랜선 자르기

 

랜선 자르기는 이진 탐색을 사용해서 문제를 해결해야한다.

만약 예제 입력만 보고 배열을 사용해 순회를 한다면 제한 시간을 초과할 수 있으며,

2 2
1
1000

인 경우 답이 500인데 검출하지 못하는 문제가 생긴다.

 

따라서 이진 탐색을 통해 left가 right보다 커지는 순간이 올때, 검사를 중단하고 답을 출력한다.

 

결국 left를 1로 right를 802로 설정한다고 가정하면, mid(중앙 값)를 계산한 후, mid가 정답인지를 고려하여, left, right를 적절히 옮겨야한다.

또한 mid가 정답인지는 알 수 있는 방법은 802, 743, 457, 539를 mid로 나누어, 몫의 합이 11보다 크거나 같은지 검사한다.

 

주의할 점은 mid가 11보다 크거나 같다고, 바로 최대값이 나오지 않을 수 있다.

따라서, mid가 11보다 크거나 같다면, left를 mid보다 한 칸 다음으로 옮겨, 가능한지 검사하고 

mid가 11보다 작다면, right를 mid보다 한 칸 전으로 옮겨, 가능한지 검사하면 된다.

 

#include <iostream>
#include <algorithm>

using namespace std;

unsigned int ans;
unsigned int list[10000];

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

	unsigned int left = 1, right = maxi, mid;
	
	while (left <= right)
	{
		mid = (left + right) / 2;
        
		unsigned int now = 0; 
        
		for (int i = 0; i < K; i++)
		{
			now += list[i] / mid;
		}

		if (now >= N)
		{
			left = mid + 1;
			ans = max(ans, mid);
		}
		else
		{
			right = mid - 1;
		}
	}
	
	cout << ans << '\n';
}