hj_d   9년 전

6286 번 문제 자바로 풀고 있는데.... 피보나치 수열을 인덱스 100,000 까지 구현 해서 찾을라고 하는데 ㅜㅜ 정수 크기가 따라가지 못하는데...

혹시 배열에 인덱스 100,000까지 수열을 넣고 찾는 방식으로 하는것이 아닌가요? 아니면...... 정수 크기늘리는 방법이 있나요?

BigInteger 를 쓰려고 했는데.... 이걸로 어떻게 계산 하는지....ㅜㅜ

hahaha   9년 전

피보나치 수의 일부분인 최대 40자리만 들어온다는 것을 이용하면 됩니다.

pichulia   9년 전

100,000번째 피보나치 수를 미리 구해놓고 답을 구하려는 생각은 버리세요.. 2진수로 어찌어찌 잘 표현했다고 쳐도 모든 문자를 표현하는데 메모리가 300MB가 넘게 소모됩니다. 게다가 시간적으로 문제도 있고.....


이 문제를 풀기 위해선 피보나치 수열이 an - a(n-1) - a(n-2) = 0 이 된다는 점을 이용해서 an의 일반항을 구할 수 있어야합니다.

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