[Baekjoon] 1654번: 랜선 자르기

 

 

 

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

1654번: 랜선 자르기

 

---

 

문제 해결 과정

착안

캠프에서 사용할 랜선을 만들기 위해 목표로 하는 $N$ 개 이상의 랜선을 얻으면서, 가능한 최대의 랜선 길이를 구해야하므로 주어진 랜선 길이를 여러 번 잘라보며 최대 길이를 구해야 한다.

 

이때, 목표로 하는 $N$ 개 이상의 랜선을 만들기 위해 가장 작은 길이인 1부터 시작하여 랜선을 잘라 계산을 하다보면 주어지는 입력 값이 어떤지에 따라 랜선 길이의 최댓값을 찾는 과정이 매우 오래 소요될 수 있다. 따라서 이진 탐색(binary search, 이분 탐색) 알고리즘을 응용하여 가능한 랜선 길이의 최댓값을 구하고자 하였다.

 

구현

이진 탐색 알고리즘을 응용하면 본래 찾고자 하는 특정 수를 찾는 코드가 아닌, 특정 조건을 만족하는 수 중에서 최댓값을 찾을 때까지 계속해서 탐색을 수행하도록 구현할 수 있다(정확히는 최댓값보다 1 큰 수를 찾는다). 기존의 이진 탐색 알고리즘에서 조건을 만족하는 수를 찾았을 때 탐색을 종료하도록 하지 않고 계속해서 최댓값(또는 최솟값 탐색도 가능)을 찾도록 구현할 수 있다.

 

랜선의 길이를 $m$ 단위로 잘랐을 때 얻어지는 사용 가능한 총 랜선의 수를 $f(m)$라고 하면,

 

• $f(m) < N$ 인 경우, 랜선 수가 모자라는 것이므로 더 짧은 단위로 잘라야 한다.
• $f(m) > N$ 인 경우, 조건을 만족하므로 가능한 $m$ 의 최댓값을 찾기 위해 추가로 탐색해야 한다.
• $f(m) = N$ 인 경우, 조건을 만족하므로 가능한 $m$ 의 최댓값을 찾기 위해 추가로 탐색해야 한다.

 

즉, 이진 탐색 알고리즘에서 조건을 정확히 만족하는 경우인 세 번째 경우를 어떻게 처리하느냐에 따라서, 이진 탐색 알고리즘을 조건을 만족하는 최댓값 또는 최솟값을 탐색하는 알고리즘으로 변형이 가능하다.

 

// 앞의 코드 생략, minLen과 maxLen은 각각 탐색 구간의 왼쪽, 오른쪽 끝을 의미

while (minLen < maxLen)
{
	unsigned middle = (minLen + maxLen) / 2;
    
	if (NumLines(middle) < N)
		maxLen = middle;
	else
		minLen = middle + 1;
}

 

이때, 주의할 점은 위와 같이 이진 탐색을 응용하여 구현했을 때 이진 탐색의 결과로 탐색 구간이 하나의 숫자로 수렴하게 되는데, 이 수렴하는 값은 우리가 구하고자 하는 값보다 1이 큰 수이다. 즉, 문제에서 요구하는 답이 $M$인 경우, 이진 탐색을 통해 $(M+1)$의 값이 도출된다.

* if (NumLines(middle) < N) maxLen = middle; 코드를 잘 살펴보면 탐색 구간의 우측 끝 값은 항상 조건을 만족하지 못한다는 것을 이해할 수 있다. 한편, 우측 끝 값이 탐색 과정을 거쳐 계속해서 찾고자 하는 값에 가까워지기 때문에 결론적으로는 탐색 구간의 우측 끝 값은 반드시 $(M+1)$ 로 수렴한다.

 

따라서 위의 코드에서 사용되는 시작 탐색 구간의 우측 끝 값은 문제에서 답으로 나올 수 있는 값이 아닌, 답이 될 수 없는 값(들 중에서 가장 작은 값)이 되어야 하고 이로 인해 주어진 처음 랜선의 길이 중 가장 긴 값보다 1 큰 숫자를 시작 탐색 구간의 우측 끝 값으로 사용해야 한다.

* 추가적으로 탐색을 통해 $(M+1)$ 값이 얻어지므로 결과 값에서 1을 빼는 부분도 잊지 않도록 한다.

 

이외에 문제를 해결할 때 주의할 점은 int 형 자료형들 사이에 덧셈을 수행하는 과정에서 정수 오버플로(integer overflow)가 발생할 수 있으므로, 이러한 점이 우려되는 부분의 변수를 unsigned int 자료형으로 사용하는 것에 주의하여 구현하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int K, N;
int Lines[10000];

int NumLines(unsigned len)
{
	int count = 0;
	for (int i = 0; i < K; i++)
		count += Lines[i] / (int)len;

	return count;
}

int main()
{
	cin >> K >> N;

	unsigned minLen = 1;
	unsigned maxLen = 0;
	for (int i = 0; i < K; i++)
	{
		cin >> Lines[i];
		if (maxLen < Lines[i])
			maxLen = Lines[i];
	}

	maxLen++;
	while (minLen < maxLen)
	{
		unsigned middle = (minLen + maxLen) / 2;

		if (NumLines(middle) < N)
			maxLen = middle;
		else
			minLen = middle + 1;
	}

	cout << maxLen - 1 << "\n";
	return 0;
}

 

실행 결과