글 읽기 - [3649][로봇 프로젝트] 25%에서 시간초과

plm2034 4년 전 0

25%에서 시간초과가 뜹니다.

정렬과정이 문제일까요?

어느 부분이 문제인지, 그리고 해결 위한 힌트좀 주세요.

#include <stdio.h>
#include <stdlib.h>

int bi_search(int* length, int start, int end, int find) {
	if (start == end) {
		if (length[start] == find) {
			return start;
		}
		return -1;
	}

	if ((start - end) * (start - end) == 1) {
		if (length[start] == find) {
			return start;
		}
		if (length[end] == find) {
			return end;
		}
		return -1;
	}

	if (length[(start + end) / 2] > find) {
		return bi_search(length, start, (start + end) / 2, find);
	}
	return bi_search(length, (start + end) / 2, end, find);
}

int main() {
	int target;
	int n;
	int* length;
	int i, j;
	int temp;
	int end;

	while (1) {
		end = 0;
		scanf("%d", &target);
		scanf("%d", &n);
		if (n < 2) {
			printf("danger\n");
			end = 1;
		}
		if (end == 0) {
			length = (int*)malloc(sizeof(int) * n);
			for (i = 0; i < n; i++) {
				scanf("%d", &length[i]);
			}
			for (i = 0; i < n; i++) {
				for (j = i + 1; j < n; j++) {
					if (length[i] > length[j]) {
						temp = length[i];
						length[i] = length[j];
						length[j] = temp;
					}
				}
			}
			for (i = 0; i < n; i++) {
				temp = bi_search(length, i + 1, n - 1, target * 10000000 - length[i]);
				if (temp != -1) {
					printf("yes %d %d\n", length[i], length[temp]);
					free(length);
					end = 1;
					break;
				}
				else if (length[i] + length[j] > target * 10000000) {
					break;
				}
				if (end == 1) {
					break;
				}
			}
			if (end==0) {
				free(length);
				printf("danger\n");
			}
		}
	}
	return 0;
}

djm03178 4년 전 1

네, 정렬이 문제입니다. 버블 정렬은 O(N^2)이기 때문입니다. O(N^2)에 정렬할 거면 차라리 정렬을 안 하고 이분 탐색도 안 하는 게 낫습니다.

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

문제

문제

출처

ICPC

[3649][로봇 프로젝트] 25%에서 시간초과

plm2034 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말