글 읽기 - 01타일 문제 질문

gumdung 6년 전 0

피보나치문제 아닌가요??

1->1,2->2,3->3,4->5 ~~~~~~~~~

그래서 dp를 이용해 피보나치 코드를 작성했는데 수가 커지니 이상하게 음수가 나오거나 갑자기 오류가 뜨더라구요...

int형식이 문제인가 싶어서 long long 형으로 변환시켜줬는데도 똑같은 문제가 반복됩니다.

어떻게 해결해야 될까요.

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

long long dp[1000001];
long long pivo(long long num);

int main()
{
	long long num,x;
	scanf("%lld",&num);
	
	x=pivo(num);
	
	printf("%lld",x%15746);
	
	return 0;
}
long long pivo(long long num)
{
	long long rev;
	
	if(num==1)
		return 1;
	if(num==2)
		return 2;
	if(dp[num]!=0)
		return dp[num];
	else
	{
		rev=pivo(num-1)+pivo(num-2);
		dp[num]=rev;
		return rev;
	}
}

chogahui05 6년 전 1

나머지 연산을 하셔야죠.. 100만 자리까지 간다면.. 나머지 연산을 안 하셨어요..

대충 계산을 해 봅시다. 피보나치 수열을 a(n)이라 하면

a(n)/a(n-1) = 대충 1.618... 에 수렴하니까 대충 1.6이라고 쳐 보면..

1.6^100만이 대충 몇 자리인지만 알면 됩니다.

100만 * log1.6 = 대충 20만 자리네요..

chogahui05 6년 전 1

pivo 함수 안에서 나머지 연산을 하셔야 해요~

최종 결과치에 나머지 연산을 하면

이미 오버플로우 되어서 잘못된 값이 나왔는데.. 의미가 없거든요..

gumdung 6년 전 0

ㅎㅎ해결했습니다!!정말 감사드립니당

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

문제

문제

출처

ICPC

01타일 문제 질문

gumdung 6년 전 0

chogahui05 6년 전 1

chogahui05 6년 전 1

gumdung 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말