[백준] 15624 피보나치수 7

URL : https://www.acmicpc.net/problem/15624

15624번: 피보나치 수 7

문제 살펴보기

피보나치 관련 문제이다. 입력은 첫줄에 n이 주어지고 이 n은 1000000보다 작거나 같은 자연수 또는 0이다.

 

출력은 n번째 피보나치 수를 1000000007로 나눈 나머지를 출력하는 것이다.

 

문제 풀이

우선적으로 큰 수에 대한 피보나치 수이므로, 처음에 동적계획법을 이용해서 접근하였다.

import sys
sys.setrecursionlimit(10**6)
saved = [None] * 10000001

def fibonacci(x):
    if x == 0:
        return 0
    if x <= 2:
        return 1
    else:
        if saved[x]:
            return saved[x]
        else:
            saved[x] = fibonacci(x - 1) + fibonacci(x - 2)
            return saved[x]

print(fibonacci(int(sys.stdin.readline())) % 1000000007)

하지만 이런 방식으로 접근하게 되면, 메모리 초과 오류가 뜬다. 이 문제는 아래 원리를 사용해야한다.

 

예를 들어 아래 피보나치 수열을 보자.

 

1 1 2 3 4 5 13 21 34 55 89 144

 

만약 여기서 11번째(89)를 11 로 나눈 나머지 값을 출력하라고 가정하면, 나머지값 1이 나온다.

 

이걸 나머지 분배법칙으로 풀어보면 아래와 같이 수열을 작성할 수 있다. 이 문제는 모듈러 연산과 연관이 있는 문제이며, 이 링크로 들어가면 더 자세히 볼 수 있다

https://sexycoder.tistory.com/66

모듈러 연산의 성질과 증명

 

1)

1 + 1 % 11 -> 2

 

1 1 2

2) 

(1 + 2) % 11 -> 3

 

1 1 2 3

3)

(2 + 3) % 11 -> 5

 

1 1 2 3 5

4)

(3 + 5) % 11 -> 8

 

1 1 2 3 5 8

5) 

(5 + 8) % 11 -> 2

 

1 1 2 3 5 8 2

6)

(8 + 2) % 11 -> 10

 

1 1 2 3 5 8 2 10

 

7)

(2 + 10) % 11 -> 1

 

1 1 2 4 5 8 2 10 1

 

8)

(10 + 1) % 11 -> 0

 

1 1 2 4 5 8 2 10 1 0

 

9)

(1 + 0) % 11 -> 1

 

1 1 2 4 5 8 2 10 1 0 1

 

결론적으로 피보나치 수열의 각 자리의 나머지 값들로 피보나치 수열을 구현하면 동일한 값이 나오는것을 볼 수 있다. 구현은 아래와 같다.

import sys


def fibo(x):
    if x == 0:
        return 0
    a = 1
    b = 1
    res = 0
    for _ in range(x - 2):
        tmp = b
        b = (a + b) % 1000000007
        a = tmp
    return b

print(fibo(int(sys.stdin.readline())))