백준 1654(랜선 자르기)

정확히 작년 5월 26일 부터 틀린 문제. 

이분탐색을 접하면서 가장 많이 틀린 문제고 오늘 드디어 정답을 맞췄다. 

 

이 문제가 이분탐색이란걸 문제보고 안 것은 아니지만 이분탐색으로 풀 수 있는 근거를 생각해보면, 문제가 정렬되어 있다? 정답으로 다가가는게 크기와 비례한다라고 해야되나 

 

풀 수 없는 문제를 생각해보면 비교하는 값이 값의 크기의 방향성과 상관없다고 말하면 될 것 같다.

 

 

이분탐색은 정렬된 수에서 원하는 값을 보다 빠르게 찾을 수 있다. 

소주 병뚜껑 숫자 맞추기 하듯이 중간값을 계속 대입하여 log n의 속도로 값을 찾는다.

 

코드를 구성하는데 가장 중심은

 

1. 빠뜨리는 수가 없이 탐색을 하느냐

2. 그 수가 조건에 맞는 수냐

 

이 두가지 조건이었다.

 

2번 조건은 잘 구성해서 짠 것 같았지만 

계속해서 틀렸고, 조금씩 변경해서 코드를 짠 결과 이분탐색할때 완벽히 탐색하려면 두 가지 케이스로 나뉜다고 알게 되었다.

 

1. while(right >= left)

  left = mid+1;

  right = mid -1;

 

2. while(right > left)

  left = mid;

  right = mid;

 

2번 케이스로 진행을 하다보면 {0, 1} 에서 1을 찾으려는 경우 찾지 못하는 경우가 발생한다.

 

아래 코드에서는 추가 조건문을 추가해서 제대로 찾는 것 같지만 다른 문제 풀어본 결과 1번 식으로만 돌리는게 맞다는 생각이 든다.

 

왜인지는 정확히 반례로 찾지는 못 했지만 위 두가지 말고 섞어서 제출하는 경우 모두 틀렸습니다. 로 나왔다. 

 

아래는 제일 처음 성공한 코드

 

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 10001
#define ll long long

ll K, N;
ll lan[MAX];
ll right_n, left_n, mid,sum=0,num, max_n=0, tmp=0;


int main() {
	cin >> K >> N;
	for (int i = 0; i < K; i++) {
		cin >> lan[i];
		sum += lan[i];
		tmp = max(tmp, lan[i]);
	}
	left_n = 1;
	right_n = sum/N;
	while (right_n >= left_n) {
		mid = (right_n + left_n) / 2;
		num = 0;
		for (int i = 0; i < K; i++) {
			num += lan[i] / mid;
		}
		if (num >= N) {
			left_n = mid + 1;
			if (mid > max_n)
				max_n = mid;
		}
		else { 
			right_n = mid - 1;
		}

	}
	cout << max_n << "\n";
}

가장 작을 수 있는 값을 left_n에 1로 두고, 경우의 수 중 가장 클 수 있는 값은 단순 길이의 합을 원하는 갯수로 나눈 값으로 설정하였다. 

 

그 뒤에 이분탐색을 하면서 N이상의 값을 가질 때 조건을 만족하면서 가장 큰 값을 max_n으로 하였고 그 값을 출력한다.

 

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 10001
#define ll long long

ll K, N;
ll lan[MAX];
ll right_n, left_n, mid, sum = 0, num;


int main() {
	cin >> K >> N;
	for (int i = 0; i < K; i++) {
		cin >> lan[i];
		sum += lan[i];
	}
	left_n = 1;
	right_n = sum/N;
	mid = (right_n + left_n) / 2;
	while (right_n > left_n) {
		num = 0;
		for (int i = 0; i < K; i++) {
			num += lan[i] / mid;
		}
		if (num >= N) {
			mid += 1;
			num = 0;
			for (int i = 0; i < K; i++) {
				num += lan[i] / mid;
			}
			if (num < N) {
				mid -= 1;
				break;
			}
			else {
				left_n = mid;
			}
		}
		else { 
			right_n = mid;
		}
		mid = (right_n + left_n) / 2;
	}
	cout << mid << "\n";
}

위 코드는 while 조건을 변경한 코드로 

mid의 값이 만족할 때 mid+1이 만족하지 않는다면 mid를 출력하여 정답을 구한다. 

 

 

어떤 문제가 이분탐색 같다면 위에서 언급한 두 케이스를 잘 생각하자. 

경계값도 잘 설정하고.