[알고리즘] C++ 백준 1654 랜선 자르기

백준 1654

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

1654번: 랜선 자르기

풀이 전 나의 생각

주어진 K개의 랜선들을 어떤 값으로 나눠서 목표 랜선 개수 N개를 만들어야한다.

또한 나눠야 하는 값은 최댓값이어야한다.  

 

일반적으로 생각해보면 1부터 랜선의 최대 길이 만큼 탐색하면서 모든 길이를 나누면 될 것같다.

하지만 랜선의 길이는 2^31 - 1 이기 때문에 약 21억번 만큼 탐색을 진행하며 10000개의 랜선을 나눈다고 가정하면

21억 * 10000 의 계산을 진행해야 하니 시간제한을 맞추지 못할 것이다.

 

따라서 O(logN)의 속도를 가지는 이분탐색을 사용해야 한다.

 

그럼 나눠야 할 어떤 값을 구해야 하는데 이 값은 1부터 랜선의 최고 길이값 안에 포함되있을 것이다.

예를 들어 랜선의 개수가 4개이며 각각의 길이는 802, 743, 457, 539가 있다면 1부터 802 범위 안에

찾고자 하는 값이 무조건 있을 것이다.

 

그럼 최댓값인 802를 기준으로 이분탐색을 진행해야하니

초기 시작점은 1이되며 끝점은 802가 될 것이다.

그렇기 때문에 (시작점 + 끝점) / 2 를 하여 중간점을 얻어내고

이 값을 이용하여 주어진 모든K개의 랜선을 중간점 값으로 나눠 준다.

 

이 후 나눠준 모든 값을 담아준 공간 sum이 있다고 가정하자.

sum이 목표 개수보다 크거나 같다면 최종 결과값에 중간점 값을 넣어주며

계속 갱신시키고 시작점을 중간점 + 1로 설정해준다.

그 이유는 결국 목표 개수 N개를 맞추며 나눠야 하는 최대의 값을 구하려면

sum이 n보다 큰 수에서 계속 내려오면서 최종값을 갱신해줘야 최대의 값을 구해낼 수 있기 때문이다.

 

반대로 sum이 n보다 작다면 값이 증가하며 중간점을 찾기 때문에 최댓값을 갱신 시켜주지 않고

끝점을 중간점 + 1로 설정하고 다음 탐색을 진행한다.

 

이런 과정을 시작점이 끝점보다 값이 높아질 때 까지 탐색을 완료한다면 나눌 수 있는 최대값을 

구해낼 수 있다.

 

여기서 주의해야할 점은 시작점을 1로 설정해야 한다는 것이다. 

기본적으로 1부터 랜선 최대길이 만큼 탐색을 하는 이유도 있지만

0부터 탐색을 한다면 랜선의 길이가 1일 때 (0 + 1) / 2를 하면 중간값이 0이되고

그렇게 랜선의 값에 0을 나누는 과정이 진행되어 DivisionByZero 오류가 발생하게된다.

 

해결법으로는 중간값이 0일 때 sum의 값을 현재 설정한 타입의 MAX값으로 설정하고 나누는 과정을

예외시켜주면 해결되긴 한다.

 

그리고 두번째 주의해야할 점은 랜선의 길이가 2^31 - 1이라고 하여 모든 변수의 타입을 int로 설정하면 안된다.

시작점과 끝점을 다루는 계산 특성상 중간값과 관련된 모든 변수는 값의 오버플로우가 발생할 수 있기 때문에

int보다 큰 unsigned나 long 형으로 바꿔서 사용해야한다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;
long lan[10001];

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

	int k, n, ans = 0;
	long start = 1;
	long end = 0;

	cin >> k >> n;

	for (int i = 0; i < k; i++)
	{
		cin >> lan[i];
		end = max(end, lan[i]);
	}

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

		for (int i = 0; i < k; i++)
		{
			sum += lan[i] / mid;
		}

		if (sum >= n)
		{
			ans = mid;
			start = mid + 1;
		}
		else
		{
			end = mid - 1;
		}
	}

	cout << ans;
}