백준 2749번: 피보나치 수 3 (Python)

접근

https://www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

n으로 주어지는 숫자가 매우 큰것을 보고, 이것은 그냥 알고리즘으로 풀 수 없다는 것을 어렴풋 느끼고 무조건 무언가 주기가 있겠구나 하고 접근하기 시작했다. 피보나치 수가 0으로 시작하므로 처음으로 0이 나오는 피보나치 수를 찾아 주기성을 보려고 했는데 틀렸다.

N = int(input())
mod = 1000000
fib = [0, 1]

i = 2
while 1:
    fib.append(fib[i - 2] + fib[i - 1])
    fib[i] %= mod
    if fib[i] == fib[0]:
        break
    i += 1

print(fib[N % (i - 1)])

혹시나 싶어 두개 연속으로 일치할 때를 주기로 설정하니 정답은 맞았다.

N = int(input())
mod = 1000000
fib = [0, 1]

i = 2
while 1:
    fib.append(fib[i - 2] + fib[i - 1])
    fib[i] %= mod
    if fib[i] == fib[1] and fib[i - 1] == fib[0]:
        break
    i += 1

print(fib[N % (i - 1)])

맞았긴 한데 찜찜하여 확인해보니 피사노 주기라는게 있다고 한다.. 피보나치 수를 일정한 수로 나눌때 그 나머지가 일정한 주기를 갖는다는 것인데 그 나누는 수가 10^k 일 때, 피사노 주기는 15 * 10^(k - 1) 이라고 한다. 즉 문제에서 나누는 수는 1,000,000이므로 피사노 주기는 1,500,000으로, 1,500,000번마다 같은 나머지가 나오게 된다.

처음에 풀었던 1번 코드의 주기를 확인해보니 750,000으로 나오는 것으로 보아, 750,000 이상의 수가 인풋으로 주어지면 오답이 나올 수 밖에 없었음을 알 수 있었다. 반면에 2번 코드의 주기를 확인해보니 1,500,000 으로 정확히 주기를 파악하여 정답이 나왔다. 피사노 주기를 이용하여 작성한 정답 코드는 아래와 같다.

코드

N = int(input())
mod = 1000000
fib = [0, 1]
p = mod // 10 * 15

for i in range(2, p):
    fib.append(fib[i - 2] + fib[i - 1])
    fib[i] %= mod

print(fib[N % p])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!