[백준][1654] 랜선 자르기

요구사항 분석

사용자는 길이가 다른 K개의 랜선을 알려주고
주어진 랜선들로 동일한 길이의 랜선을 최소 N개 이상을 충족하면서 최대 개수를 만들고자 할 때,
최대 개수에서의 랜선 길이를 출력하는 것이 이번 문제의 요구사항 입니다.

K는 1이상 10’000이하 정수, N은 1이상 1’000’000이하 정수, K $\leq$ N이며 랜선의 길이는 2³¹ -1 이하이다.

알고리즘 선택

목표 랜선 길이를 구하기 위해 먼저 전체 랜선 길이의 합을 구하고 N으로 나누어
목표 랜선 길이의 최대값을 구하였습니다.
그리고 최대값의 맨 앞자리 숫자가 변경되기 전 마지막 숫자를 최소값으로 설정 하였습니다.
마지막으로 순차탐색 을 이용해 최대값부터 최소값까지의 길이 중 하나씩 선택하여 주어진 K개의 랜선을 각각 나눈 몫의 합이 최대인 선택된 목표 랜선의 길이를 출력하고자 하였습니다.

풀이 분석

위의 설명처럼 순차탐색 을 이용해서 목표 랜선을 출력하는 프로그램을 구현하였습니다.

#include <iostream>
#include <cmath>

int main() {
	int K = 0, N = 0, sum = 0;
	std::cin >> K >> N;
	int* arr = new int[K];

	for (int t = 0; t < K; ++t) {
		std::cin >> arr[t];
		sum += arr[t];
	}

	int maxVal = sum / N;
	int minVal = maxVal;
	int pos = 0;
	for (; minVal >= 10; ++pos) minVal /= 10;
	minVal = minVal * pow(10, pos);

	int maxCnt = 0;
	int maxLen = 0;
	for (int v = maxVal; v >= minVal; --v) {// ... (1)
		int currCnt = 0;

		for (int i = 0; i < K; ++i) {		// ... (2)
			currCnt += (arr[i] / v);
		}
		if (currCnt > maxCnt){
			maxCnt = currCnt;
			maxLen = v;
		}
	}

	std::cout << maxLen;
}
  

위의 코드는 치명적인 문제점이 존재합니다.
주어진 테스트 케이스 혹은 적은 범위의 테스트는 통과할 수 있지만
최악의 경우 (1)번과 (2)번 반복문 모두 10’000번 순회할 경우 1억번 순회를 할 수 있습니다.
따라서 이 문제는 순차탐색이 아닌 검색 속도가 빠른 알고리즘 을 선택해야 합니다.

최적화

특정한 범위에서 빠른 검색을 실행할 수 있는 이진 탐색 을 통해 구현해보았습니다.

#include <iostream>

int main() {
	int K, N;
	long max = 1;
	std::cin >> K >> N;
	int* arr = new int[K];
	for (int i = 0; i < K; ++i) {
		std::cin >> arr[i];
		if (arr[i] > max) max = arr[i];
	}

	++max;
	long min = 0, mid = 0;

	while (min < max) {
		mid = (max + min) / 2;
		
		long cnt = 0;
		for (int i = 0; i < K; ++i) {
			cnt += (arr[i] / mid);
		}

		if (cnt < N) {
			max = mid;
		}
		else {
			min = mid + 1;
		}
	}

	printf("%d", min - 1);
}