글 읽기 - 출력값은 같게 나오는데 틀렸다고 떠요

어떤부분이 틀린건지 잘 모르겠어요...

n = int(input())

a=0
b=1

for i in range(n):
    c = a + b
    a = b
    b = c

    
print(a%1000000)

n제한이 무려 100경 입니다. 아무리 나눈다고해도 결국 long long 범위를 가볍게 넘어가기때문에 오류가 발생합니다.

피사노 주기에 대해 공부해보고 다시 풀어보는게 좋을것같습니다. 참고로 int 범위는 약21억으로 이문제를 풀기는 터무니 없이 낮습니다.

피보나치 값을 10^k 승으로 나누었을때 피보나치 값의 주기는 15 * 10^(k-1)라는 성질을 이용해서 풉니다.

이문제에서는 k가 6이므로 주기는 150만이 됩니다. 그러니까 150만번째까지 피보나치만 구해서 그 이상의수는 배열 인덱스 나머지150만을 하면 구할수있습니다.

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

Baekjoon Online Judge