백준 1654번 : 랜선 자르기 [C언어]

문제출처

https://www.acmicpc.net/problem/1654

 

우선 나는 문제를 보고 5분안에 생각이 안나면 다른 라이트업들을 찾아보는 중이라...

이런 문제는 이진탐색을 이용해서 풀어야 한다는 점을 배웠다.

처음에 작성한 코드다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 100001
int main()
{
	int k, n;
	long long kLength[MAX];
	int i;
	long long right = 0, left = 0;
	long long mid;
	int result = 0;

	scanf("%d %d", &k, &n);
	for (i = 0; i < k; i++) {
		scanf("%lld", &kLength[i]);
	}

	//right찾기
	for (i = 0; i < k; i++) {
		if (right < kLength[i])
			right = kLength[i];
	}

	while (1) {
		mid = (left + right) / 2;
		for (i = 0; i < k; i++)
			result += kLength[i] / mid;

		if (result >= n) break;
		else {
			result = 0;
			right = mid;
		}
	}

	printf("%d\n", mid);

}

틀렸다. 예제로 나와있는건 맞게 돌아갔다.

추측해본 틀린 이유는 

랜선 길이를 더 길게 할 수 있는 부분을 탐색하지 않고 끝나는 거 같다.

else에서 right를 mid로 줄여줬기 때문에 나의 경우에는 왼쪽 부분만 계속 탐색하게 되는데

오른쪽 부분에 답이 있을 수도 있는 경우가 생길 수 있을거 같다.

 

무조건 n개 이상을 만들면 되는게 아니라 <최대 랜선의 길이>를 구해야하니까...

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 100001
int main()
{
	int k, n;
	long long kLength[MAX];
	int i;
	long long right = 0, left = 1;
	long long mid;
	int count = 0, result = 0;

	scanf("%d %d", &k, &n);
	for (i = 0; i < k; i++) {
		scanf("%lld", &kLength[i]);
	}

	//right찾기
	for (i = 0; i < k; i++) {
		if (right < kLength[i])
			right = kLength[i];
	}

	while (left <= right) {
		mid = (left + right) / 2;
		for (i = 0; i < k; i++)
			count += kLength[i] / mid;

		if (count < n) {
			right = mid - 1;
		}
		else {
			if (result < mid) 
				result = mid;
			left = mid + 1;
		}
		count = 0;
	}

	printf("%d\n", result);

}

1.while문의 조건을 left <= right로 바꿔주고

2.count가 n보다 작다면 : 랜선을 더 잘게 쪼개야 한다는 말 즉 right의 범위를 줄여야함

3.count가 n보다 크다면 : 정답이 될 수도 있고 더 길게 자를 방법이 있을 수 있음 오른쪽 부분을 탐색해야함

4.따라서 만약 mid가 기존에 찾아준 정답 보다 큰지 검사 후 result에 값을 저장해둠

 

이렇게 거쳐서 돌렸는데 런타임 에러가 나와서 찾아보니 left를 0이 아니라 1로 두어야 한다고 한다.

left가 0이면 right가 1일때 mid가 0이 되는 경우가 생길 수 있는데 그러면 count를 계산 하는 부분에서 kLength를 0으로 나누는 일이 생길 수 있어서 런타임 에러가 발생한다고 한다.