글 읽기 - 이분탐색인데 시간초과....도와주세요

minuk6219 7년 전 0

안녕하세요 제가 이분탐색으로 풀었는데도 시간초과가 계속 나길래

다른사람 코드를 찾아봤습니다.

근데 비교 결과 제 코드와 동작 원리는 똑같고, 시간 차이가 날만한 곳이 보이지 않는데,...

무엇때문에 제 코드는 시간초과이고 정답코드는 정답으로 제출되는지 알수있나요???

#include<iostream>
	#include<cstdio>
	#include<algorithm>
	using namespace std;

	long long K, N, lan[10000];
	int check(int n) {
	int cnt = 0;
	for (int i = 0; i < K; i++)
	cnt += lan[i] / n;
	return cnt >= N;
	}

	int main() {
	long long left = 1, right = 0, mid, ans = 0;
	scanf("%d %d", &K, &N);

	for (int i = 0; i < K; i++) {
	scanf("%d", &lan[i]);
	if (lan[i] > right)
	right = lan[i];
	}

	while (left <= right) {
	mid = (right + left) / 2;
	if (check(mid)) {
	if (ans < mid)
	ans = mid;
	left = mid + 1;
	}
	else {
	right = mid - 1;
	}
	}

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

	return 0;
	}

이 위에 써있는게 정답코드이고, 밑에 써져있는게 제 코드입니다ㅜㅠ

#include<cstdio>

int lan[10001];

int main(void)
{
	int n,k;
	int ans=0;
	int start = 1;
	int end = 0;
	int cnt = 0;
	scanf("%d %d",&k, &n);
	long long sum = 0;
	for(int i = 0 ; i < k ; i++){
		scanf("%d",&lan[i]);
		if(lan[i] > end)
			end = lan[i];
	}

	while(start <= end)
	{
		int mid = start + (end - start)/2;
		cnt = 0;
		for(int i = k-1; i >= 0 ; i--)
		{
			cnt += (lan[i] / mid);
		}
		if(cnt < n){
			end = mid-1;
		}
		else
		{
			if(mid > ans)
				ans = mid;
			start = mid+1;
		}
	}
	printf("%d",ans);
	return 0;
}

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