글 읽기 - 시간초과 질문입니다

comdori 9년 전 0

C언어로 피보나치 몇번째인지 확인하는 코드를 짰는데 시간초과가 뜨네요.

어떤 부분을 고쳐야 할지 모르겠는데 도와주세요 ㅠㅠ.ㅠ

아마도 while문이 문제겠죠?

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

int fibo(int n)
{
	int result;
	int count = 1;
	int arr[2];

		arr[0] = 1;
		arr[1] = 1;
		result = 1;
		count++;
			
		if (n == result)
		{
			return count;
		}
				
	

		{
			while (1)
			{
				result = arr[0] + arr[1];
				arr[0] = arr[1];
				arr[1] = result;
				count++;
				if (n == result)
					return count;
			}
		}
}

int main(void)
{
	int fibnum;
	int num;
	int i;
	int* arrr;

	scanf("%d", &num);
	arrr = (int*)malloc(sizeof(int)*num);
	for (i = 0; i < num; i++)
	{
		scanf("%d", &arrr[i]);
		arrr[i] = fibo(arrr[i]);
	}

	for (i = 0; i < num; i++)
		printf("%d\n", arrr[i]);

	free(arrr);

	return 0;
}

hahaha 9년 전 1

인풀이 1 ≤ Fn ≤ 10^21000이 들어오는데 int로 받는 것이 잘못된 것 같습니다. 또한 같은 이유로 int로 표현할 수 없는 범위의 피보나치수는 위의 방법으로는 찾을 수 없네요ㅜ

hahaha 9년 전 1

인풀>>인풋 정정

amugeona 9년 전 2

대충 숫자보고 찍어맞춰도 정답 나올거에요;;;

comdori 9년 전 0

@hahaha 그럼 long int같이 더 큰것으로 받아야 한다는 말씀이신가요??

@amugeona 대충 숫자보고 찍어맞춘다는게 무슨 뜻인가요???

hahaha 9년 전 1

피보나치 수가 너무 커서 long long로도 부족해요

해결할 수 있는 방법이 두가지가 있는데요,

1. Biginteger를 사용한다. 혹은 biginteger를 구현한다.>> 실제 자바로 푸신푼이 빅인티져로 푸셨다고 들었습니다.

2. 피보나치 수의 특징을 이용한다. 피보나치의 자리수의 일부분을 비교했을 때, 잘 겹치지 않습니다. 이걸로 때려맞추는 겁니다.

comdori 9년 전 1

@hahaha 답변감사드려요 이제 이해가 되네요~~

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