글 읽기 - 이분탐색을 잘못한건가요?

kdy312 6년 전 0

이분탐색으로 해결할 수 있는 문제들이 많아서 공부를 하고 문제를 풀고있습니다.

처음에는 시간초과가 떳기 때문에 이를 수정하였더니 드디어 틀렸습니다가 나오기 시작했습니다.

그런데 왜 틀렷는지 감이 잡히지가 않습니다

이분탐색이 잘못된것인지, 아니면 어디가 잘못된 것인지 모르겠습니다 ㅠ

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() 
{
	vector<long long> lan;
	int have = 0;
	int need = 0;
	int make = 0;
	long long length = 0;
	long long cut = 0;
	
	cin >> have >> need;

	for (int i = 0; i < have; i++) 
	{
		cin >> length;
		lan.push_back(length);
	}

	sort(lan.begin(), lan.end());

	long long cut1 = 0;
	long long cut2 = lan[0];
	
	while (cut1 != cut2)
	{
		cut = (cut1 + cut2) / 2;
		make = 0;

		for (int j = 0; j < have; j++)
			make += lan[j] / cut;

		if (make < need)
			cut2 = cut - 1;
		
		else if (make >= need)
			cut1 = cut + 1;
	}

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

	return 0;
}

ntopia 6년 전 1

계산 과정 중에 make 변수도 int 범위를 넘어설 수 있습니다.

long long 으로 바꿔보세요.

ntopia 6년 전 1

그리고 cut가 long long 형 변수인데

밑의 출력에서는 %d 로 출력하고 있네요.

이러면 구현체에 따라서는 제대로 출력되지 않을 수도 있습니다.

%lld 를 사용하세요

kdy312 6년 전 0

둘다 바꾸어 보았는데 역시나 틀렸습니다

ntopia 6년 전 1

죄송합니다. 다른 잘못된 부분을 찾았어요. 댓글 정리해서 달게요

djm03178 6년 전 1

2 2

1

4

이면 답이 2가 나와야 하는데 런타임 에러가 납니다.

ntopia 6년 전 5

1.

cut2의 초기값은 lan 배열 중에 제일 큰 값을 사용하여야 합니다.

실제로 K=1 이라면 제일 큰 랜선 하나만 그대로 사용하는게 답이 되기 때문이죠.

2.

cut1의 초기값은 1이상이어야 합니다.

cut1의 초기값을 0 으로 주면 실제로 cut이 0이 되는 경우가 생기고

이러면 0으로 나누는게 돼서 런타임에러가 나겠죠.

3.

이분탐색을 저런 식으로 하실거면

조건문을 cut1 <= cut2 로 바꾸시고 (역전되는 경우가 생깁니다)

마지막 답은 cut을 사용하는게 아니라 cut2를 사용해야 합니다.

왜 이렇게 해야하는지는 그림을 그려서 한번 잘 생각해보세요.

djm03178 6년 전 2

헉 2번은 제가 추가한 함정 데이터가 있는데 여기서 스포를 하시네요 흑흑

kdy312 6년 전 0

그런 경우의 수들이 존재하는군요...

역시 공부를 더 해야겠습니다.

감사합니다.

kdy312 6년 전 0

3번에 대해서 질문을 드리고 싶습니다

3번에 역전이 생기는 경우가 생긴다고 하셨는데,

제 소스는 역전이 생기지 않는 다면 반복이 종료되지 않기 때문에 무조건 생겨야 하는것 아닌가요?

그리고 cut2가 정답이 되어야 하는 이유는 역전이 생기기 때문에 cut은 이미 지나가 버렸고,

이를 감싸고 돌고 있는 숫자가 정답이 되기 때문인가요?

ntopia 6년 전 1

역전이 되어도 cut1 != cut2 를 만족하기 때문에 무한루프를 돌게 됩니다

chogahui05 6년 전 1

kdy님.

결정 함수를 따로 만들어 보아요.

저는 이분탐색 문제를 풀 때

무조건 결정함수 f(x)를 만듭니다.

kdy312 6년 전 0

결정함수를 만들어 본적이 없어서요...

어떤 식으로 작성 할 수 있는 건가요?

chogahui05 6년 전 1

정렬되어 있는 배열에서 1보다 작은 최초의 지점을 리턴해야 한다고 쳐 봅시다.

결정해야 하는 건 1보다 작은가죠?

int f(x) {

return (arr[x]<1);

}

kdy312 6년 전 0

아... 감사합니당

댓글을 작성하려면 로그인해야 합니다.