글 읽기 - c++ 이분탐색 왜 틀린걸까요?

seungho0510 3년 전 1

배열에 입력한 랜선수 다 받아서

left 랑 right 값으로 중앙값 구한다음

getLen(int middle) 함수에서 처음 입력한 랜선의 길이를 담은 배열에서 몇개로 나눌수 있는지 구하는 함수를 짠건데

틀렸다고 나와요ㅠ

#include <iostream>

using namespace std;

int Karr[10001];

int N,K;

int getLen(int size){
	int getK = 0;
	for (int i=0; i<K; i++){
		getK+=Karr[i]/size;
	}
	return getK;
}
int main(){
	cin >> K >> N;
	int len;
	int max=-1;
	for (int i=0; i<K; i++){
		cin >> len;
		Karr[i] = len;
		if (len>max){
			max=len;
		}
	}	
	int left = 0;
	int right = max;
	int middle = (left+right)/2;	
	while (true){
		if(getLen(middle)==N){
			cout << middle;
			break;
		}
		else if (getLen(middle)<N){
			right=middle-1;
			middle = (left+right)/2;
		}
		else{
			left = middle+1;
			middle = (left+right)/2;
		}
		
	}
	return 0;
}

dldyddlwl 3년 전 3

아래에 있습니다.

int getLen(int size){            
	int getK = 0;        // 2^31-1의 범위의 숫자들의 합을 구하기 위해선 long long을 추천드립니다!
	for (int i=0; i<K; i++){
		getK+=Karr[i]/size;
	}
	return getK;
}

int left = 0; // 이 친구도 long long으로 해주세요, 혹시나 left = mid + 1 에서 오버플로우가 생길 수도 있습니다.
int right = max;       // right는 필수는 아니지만, left도 long long이니 같이 맞춰줍시다.
int middle = (left+right)/2;    // 이 친구도 마찬가지로 long long이어야 합니다 (EX 2^31-1 + 2^31-1 = 오버플로우)

if(getLen(middle)==N){    // 문제의 조건에 N 이상도 N으로 봐도 된다고 했습니다, 즉 getLen >= N 이 더 좋다고 생각합니다.
	cout << middle;    // 저희는 최댓값을 구하는 것입니다. 그런데 이분탐색 1번만에 최댓값이 바로 찾아지면 좋겠지만,
	break;   // 그렇지 않을 수 있습니다. 그러면 일단은 이 값을 기억하고 최댓값을 갱신해가며 계속 탐색해볼 가치가 있습니다.
		}

seungho0510 3년 전 0

친절하게 주석까지!!! 너무 감사해요 덕분에 맞췄습니다.

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

문제

문제

출처

ICPC

c++ 이분탐색 왜 틀린걸까요?

seungho0510 3년 전 1

dldyddlwl 3년 전 3

seungho0510 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말