[백준 파이썬] 2749 피보나치 수 3

[백준 파이썬] 2749 피보나치 수 3 

 

처음에는 이게 무슨 골드 2 문제지 하고

dp=[0,1]
n=int(input())

for i in range(2,n+1):
    dp.append((dp[i-1]+dp[i-2])%1000000)
print(dp[n])

이렇게 코드를 제출했다 결과는 메모리 초과로 실패하여 문제 조건을 확인하였다

입력이 1,000,000,000,000,000,000 작은 n에 대한 피보나치수열인데 메모리 제한이 128MB였다.

문제 답을 출력할 때 1,000,000으로 나눈 나머지를 출력한다라고 적혀있었다.

이걸 보고 난 반복되는 주기가 발생할겠다고 생각하여 

dp=[0,1]
n=int(input())

for i in range(2,4500000+1):
    dp.append((dp[i-1]+dp[i-2])%1000000)
    if ((dp[i-1]+dp[i-2])%1000000==0):
        print(i)

나머지가 0일 때 어떤수인지를 찾는 코드를 만들었다 

750000
1500000
2250000
3000000
3750000
4500000

일때 나머지가 0 이 된다는 걸 확인하여 각 수에서 +1 +2 씩 해가면서 주기를 확인해 보니 1500000 간격으로 수들이 반복되는 것을 확인할 수 있었다.

 

그래서 완성된 코드는 

dp=[0,1]
n=int(input())

for i in range(2,1500000+1):
    dp.append((dp[i-1]+dp[i-2])%1000000)
print(dp[n%1500000])

 

다른 사람들 풀이를 읽어보니 피사노 주기를 나처럼 저렇게 하나하나씩 확인해서 주기는 구하는 게 아니라 공식을 이용해서 확정적으로 주기를 구할 수 있다.

 

주기를 구하는 공식

mod = 1000000
p = mod//10*15