BOJ - 1654 랜선 자르기 해결 전략 (C++)

• 문제 링크
  백준 1654번 - 랜선 자르기

해결 전략

  본 문제를 처음 봤을 때 본인이 떠올린 '가장 직관적인 Idea'는 다음과 같았다.

1) 입력받는 랜선들의 길이를 len[i]라고 배열 처리를 할 시, 그중에서 최소값 min_L을 기억해놓는다.
2) 그 최소값부터 1까지 min_L값을 Decrement해가면서 '각 len[i]를 min_L로 나눈 몫의 합'이 n 이상인 순간 멈춘다.

  이 방식이 아마 떠올릴 수 있는 가장 Naive한 알고리즘일 것이다. 허나, 이 알고리즘은 아주 쉽게 반박할 수 있었다.

~> len값이 int형 범위만큼 가능하므로 선형 순회를 돌 시 무조건 시간 초과가 날 수 밖에 없다.

  또한, 위 알고리즘은 논리적 오류도 존재했다. 만약, 입력이

2 2
1
1000

이면, 이 알고리즘은 정답인 500을 출력해내지 못한다.

  이 반례를 맞이한 순간! 본인은 정답을 향한 알고리즘이 문뜩 떠올랐다.

len 길이 입력이 1부터 int 자료형 양수 최대 범위까지인데, 이에 대한 선형 탐색은 시간 초과가 난다. 그렇다면, 우리가 찾고 싶어하는 값을 'Binary Search'로 찾으면 어떠할까?

  이진탐색은 O(logN)이기 때문에 충분히 이를 커버할 수 있다. 위의 반례처럼, 일부 len[i]는 그냥 쓰지 않고 버리는 경우도 있으므로, 우리는 자연스럽게 다음과 같이 알고리즘을 설계할 수 있다.

1) 입력받는 랜선들의 길이를 len[i]라고 배열 처리를 할 시, 그중에서 최대값 max_L을 기억해놓는다.
2) [1, max_L] 구간에 대해 Binary Search를 수행해 우리가 찾고자 하는 값을 탐색한다.
3) 분할의 기준은, '각 len[i]를 mid로 나눈 몫의 합'이 n 이상인 순간일 것이다. 이상이면 우측(더 큰 수들의 구간)을 보고, 아니라면 좌측을 보면서 찾는 것이다.
4) 이때, 각 탐색 안에 선형 Traverse가 들어가지만, 이는 최대 10000까지의 순회이기에 빅오가 O(MlogN)이라 문제가 없다.

  이렇게, 문제 해결 알고리즘을 설계할 수 있다. 한편, 이 아이디어를 기반으로 코드를 제출했을 때, 두 번의 실패가 따랐는데, 그 이유는 다음의 Detail이 있기 때문이었다.

left==right, 즉, 이진탐색이 깨지는 순간에, 단순히 mid가 답이 아니라, mid-1이 답일수도 있다. 이는 left==right인 순간 mid를 기준으로한 '각 len[i]를 mid로 나눈 몫의 합'이 n 미만인지 체크해서 확인해야한다. 짝수/홀수의 문제이기 때문이다.

ex) 예를 들어, left=5, right=7이라 mid가 6인 상황이다. mid=6으로 인해 몫의 합이 n을 넘어서 유효했다. 그러면 이진탐색 원리에 따라 left=7, right=7인 다음 탐색이 이루어진다. 여기선 mid=7인데, mid가 7이면 몫의 합이 n 미만이 된다고 해보자. 만약, 여기서 이 상황에 대한 처리를 해주지 않으면 답을 7로 내보내게 된다. 6인데 말이다.

  위의 예외상황 처리가 이루어지면, 문제 해결이 마무리된다. 아래는 정답 코드이다.

#include <iostream>
// BOJ - 1654 Cutting LAN Cable
using namespace std;

int len[10000], k, n;

int solve(int right) {
	int left = 1, mid, div, ans = right;

	while (left <= right) {
		mid = (left + right) / 2; div = 0;
		if (left == right) {
			for (int i = 0; i < k; i++) div += (len[i] / mid);
			if (div >= n) ans = mid;
			else ans = mid - 1;
			break;
		}

		for (int i = 0; i < k; i++) div += (len[i] / mid);
		if (div >= n) left = mid + 1;
		else right = mid;
	}

	return ans;
}

int main(void) {
	int temp, max_L = 0;
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> k >> n;
	for (int i = 0; i < k; i++) {
		cin >> temp; len[i] = temp;
		if (temp > max_L) max_L = temp;
	}
	cout << solve(max_L);

	return 0;
}