[C++]백준1654번 랜선 자르기

오늘은 백준1654번 랜선 자르기 문제를 풀어보도록 하자.

정답률이 20%로 매우 저조하다. 풀어보니 왜 그런지 알 것 같다.

이분탐색에 대한 풀이가 익숙하지 않다고 생각해서 풀어보았는데 위 문제는 이분탐색의 문제적용 + 자료형의 문제 때문에 많이 틀린 것 같다.

이분탐색에 관한 문제를 더 풀어봐야겠다.

문제는 다음과 같다.

                               [접근법]
                               
                               -재귀-
1. 입력 받은 수의 가장 큰 수를 MAX값으로 설정한다. 그 후 cut함수를 돌리는데 start = 1, end = MAX로 설정한 후 mid값과의 비교를 통해 cut함수를 계속 타고 들어간다. 만일 start값이 크	  다면 더 이상 탐색이 불가능하므로 return

                               -그냥 While문-
                               
1. 마찬가지로 재귀를 while문으로 바꾼 것이다. 마지막에 answer = end를 출력해주면 된다.

                                     [코드]
                                     
                                     -재귀-
#include <iostream>
#include <algorithm>
using namespace std;
long long LAN[10001];
int K, N;
long long answer = 0, Max_length = 0;

void cut(long long start, long long end) {
	if (start > end) {
		return;
	}
	long long mid = (start + end) / 2;
	long long sum = 0;

	for (int i = 0; i < K; i++) {
		sum += LAN[i] / mid;
	}
	if (sum < N) {
		cut(start, mid - 1);
	}
	else {
		answer = max(answer, mid);
		cut(mid + 1, end);
	}
}

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

	for (int i = 0; i < K; i++) {
		cin >> LAN[i];
		Max_length = max(LAN[i], Max_length);
	}
	cut(1, Max_length);
	cout << answer;
}

                                     -while문 -
#include <iostream>
#include <algorithm>
using namespace std;
long long LAN[10001];
int K, N;
long long answer = 0, Max_length = 0;

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

		for (int i = 0; i < K; i++) {
			sum += LAN[i] / mid;
		}
		if (sum < N) {
			end = mid - 1;
		}
		else {
			start = mid + 1;
		}
	}
	answer = end;
}

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

	for (int i = 0; i < K; i++) {
		cin >> LAN[i];
		Max_length = max(LAN[i], Max_length);
	}
	cut(1, Max_length);
	cout << answer;
}