글 읽기 - 이분탐색 최대 범위에 대한 질문입니다.

sungjjhh9707 1년 전 0

52번라인에 이분탐색 범위의 최대값을 얼마로 잡아야할지 몰라서 대충 long long 범위내에서 적당히 큰 1,000,000,000,000,000,000을 넣었었는데요

그러니까 계속 틀렸다고 나왔습니다. 그래서 자꾸 생각해보니 놀이기구가 전부 30분이면서 N이 가장 최대일 때, 약 60000000000 을 저렇게 넣으니까 정답이 뜨네요.

어차피 이분탐색이면 범위값이 저정도로 아무리 커져도 시간엔 크게 상관없을거고 또한 같은이유로 재귀도 조금밖에 추가 안돼서 메모리도 상관없을 것 같은데 왜 틀렸다고 나올까요? 범위가 커지더라도 계속 줄여나가다 보면 결국 똑같은 답 나와야 하지 않나요?

#include<iostream>

using namespace std;

long long numofpeople;
long long numofrol;
long long time[10001];

long long get_riding(long long now){	//now분 까지 출발시킨 사람 수  
	int i;
	long long mok, mod; 
	long long dap=0;
	for(i=1; i<=numofrol; ++i){
		mok = now/time[i];
		mod = now%time[i];
		if(mod!=0){
			dap+=(mok+1);	
		}
		else{
			dap+=mok;	
		}
	}
	return dap;
}

long long find_clock(long long start, long long end, long long people){
	
	if(start==end){
		long long mid_riding_people = get_riding(start);
		//cout<<start<<" "<<end<<" "<<mid_riding_people<<endl;
		return start;
	}
	long long mid = (start+end)/2;
	long long mid_riding_people = get_riding(mid);
	//cout<<start<<" "<<end<<" "<<mid_riding_people<<endl;
	if(people<=mid_riding_people){
		return find_clock(start, mid, people);
	}
	else{
		return find_clock(mid+1,end, people);
	}
	
	
}
long long solve(){
	if(numofpeople<=numofrol){
		return numofpeople;;
	}
	long long choidae_clock=0;
	long long dap;
	long long i;
	long long clock = find_clock(0, 60000000001, numofpeople);
	
	long long now_riding_people = get_riding(clock);
	long long k,yeejeon_time, yeejeon_people;
	for(k=clock; k>=0; --k){
		if(now_riding_people!=get_riding(k)){
			yeejeon_people = get_riding(k);
			yeejeon_time = k;
			break;
		}
	}
	for(i=1; i<=numofrol; ++i){
		if(yeejeon_time%(time[i])==0){
			yeejeon_people++;
			if(yeejeon_people==numofpeople){
				dap = i;
				break;	
			}
			
		}
	}
	return dap;
}

int main(void)
{
	cin>>numofpeople>>numofrol;
	int i;
	for(i=1; i<=numofrol; ++i){
		cin>>time[i];
	}
	cout<<solve();
	return 0;
}

sangmin7b 9달 전 0

get_riding()에서 now/time[i]을 M번 더하면 dap값이 long long 범위를 넘어가 오버플로우가 발생할 수 있습니다.

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

문제

문제

출처

ICPC

이분탐색 최대 범위에 대한 질문입니다.

sungjjhh9707 1년 전 0

sangmin7b 9달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말