[BOJ]1654 - 랜선 자르기

1654

전체 코드

#include <iostream>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	long long k{ 0 };
	long long n{ 0 };
	long long end{ 0 };

	cin >> k >> n;

	long long* length = new long long[k];

	for (int i = 0; i < k; i++)
	{
		cin >> length[i];
		if (end < length[i])
			end = length[i];
	}
	
	long long left{ 1 };
	long long size{ 0 };

	while (left <= end)
	{
		long long count{ 0 }; // n에 가까워지는 값
		long long middle = (left + end) / 2;

		for (int i = 0; i < k; i++)
			count += length[i] / middle;

		if (count >= n) {
			if(size < middle)
				size = middle;
			left = middle + 1;
		}
		else {
			end = middle - 1;
		}
	}

	cout << size;
}

시행착오

#include <iostream>
using namespace std;

int main() {
	int k{ 0 };
	int n{ 0 };
	int size{ 0 };

	cin >> k >> n;

	int* length = new int[k];

	for (int i = 0; i < k; i++)
	{
		cin >> length[i];
		size += length[i];
	}

	size /= n;

	while (true)
	{
		int count{ 0 };

		for (int i = 0; i < k; i++)
		{
			count += length[i] / size;
		}

		if (count == n)
			break;

		size--;
	}

	cout << size;
}

while 문으로 작성했더니 시간 초과가 떴다.

알고리즘 분류란을 열어보니 이분 탐색이 있었다.

이분 탐색은 공간을 하나하나 탐색하지 않고 중간값을 비교하여 탐색한다.

이분 탐색을 적용한 코드는 다음과 같다.

#include <iostream>
using namespace std;

int main() {
	int k{ 0 };
	int n{ 0 };
	int size{ 0 };

	cin >> k >> n;

	int* length = new int[k];

	for (int i = 0; i < k; i++)
	{
		cin >> length[i];
		size += length[i];
	}

	size /= n;
	
	int left{ 1 };
	int middle{ size / 2 };

	while (true)
	{
		int count{ 0 }; // n에 가까워지는 값
		middle = (left + size) / 2;

		for (int i = 0; i < k; i++)
			count += length[i] / middle;

		if (count < n)
			size = middle;
		else if (count > n)
			left = middle;	
		else
		{
			if (size == middle+1)
				break;
			else
				left = middle;
		}
	}

	cout << middle;
}

그래도 시간초과...

결국 풀이를 구글링했는데, 조건문을 더 줄이고 줄어드는 값에 middle은 제외하는 방법으로 개선했다.

#include <iostream>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	long long k{ 0 };
	long long n{ 0 };
	long long end{ 0 };

	cin >> k >> n;

	long long* length = new long long[k];

	for (int i = 0; i < k; i++)
	{
		cin >> length[i];
		if (end < length[i])
			end = length[i];
	}
	
	long long left{ 1 };
	long long size{ 0 };

	while (left <= end)
	{
		long long count{ 0 }; // n에 가까워지는 값
		long long middle = (left + end) / 2;

		for (int i = 0; i < k; i++)
			count += length[i] / middle;

		if (count >= n) {
			if(size < middle)
				size = middle;
			left = middle + 1;
		}
		else {
			end = middle - 1;
		}
	}

	cout << size;
}

계속 고치고 제출하고 반복했다.

중간에 '틀렸습니다' 콤보를 맞았는데 int를 long long으로 바꾸니까 넘어가더라..
타입 잘 신경써야겠다 ㅠㅠ

그리고 런타임 에러 떴는데 left를 0 -> 1로 고쳐서 통과했다. middle이 left까지 내려왔을 때 0으로 나누게 돼서 에러가 발생한 듯 하다.

---

참고자료

이분탐색

매개변수 탐색

1654 c++ 풀이