[백준] 11444. 피보나치 수 6

11444번: 피보나치 수 6

 

1. 재귀를 사용하여 푸는 방법

def fib(n):
    return (0 if n == 0 else 1) if n <= 2 else fib(n-1) + fib(n-2);

n = int(input()); # 17 입력
print(fib(n)); # 결과는 1597

# 문제 11444에서의 피보나치 배열
# 0(0번째 피보나치 수), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597(17번째 피보나치 수)

python을 안 쓴지 한참 되어서 까먹었는데, python에서는 삼항 연산자를
[True일 경우] if [조건문] else [False일 경우]와 같이 사용한다.
즉, 조건문이 if문과 else 사이에 오는 것이다. (좀 특이하다...)

여하튼 재귀를 사용해서 푸는 방법은 런타임 에러가 난다.
(그 이유는 재귀의 깊이가 깊어서라고 한다. 아래 링크 참조.)

파이썬 - 런타임 에러 (RecursionError) 해결법

 

2. 반복문으로 코드 짜기

fib(5)를 호출한다고 했을 때,
fib(5) = fib(4) + fib(3)
그리고 fib(4) = fib(3) + fib(2)이다.

이것만 생각해보아도 fib(3)과 같이 같은 값들이 두 번 이상 계산된다는 것을 확인할 수 있다.

출처: https://ko.javascript.info/task/fibonacci-numbers

피보나치 수 계산하기

def fib(n):
    a = 1;
    b = 1;
    for i in range(3, n + 1):
        c = a + b;
        a = b;
        b = c;
    return b;

n = int(input()); # 17 입력
print(fib(n)); # 결과는 1597

# 문제 11444에서의 피보나치 배열
# 0(0번째 피보나치 수), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597(17번째 피보나치 수)

그러므로 위와 같이 코드를 짜면...
시간 초과가 난다 (아니 진짜 왜지)

역시 골드 문제는 만만치 않다.

 

3. 행렬을 이용하여 문제 해결하기

[백준] 11444번 피보나치 수 6 - PYTHON

 

위 링크를 토대로 코드를 작성하면...
아래와 같이 나온다.
이제부터 아래와 같은 코드가 왜 나왔는지 생각해보자.

import sys


def mat_pow(mat, n):
    if n == 0:
        return mat;
    elif n == 1:
        return mat;
    else:
        tmp = mat_pow(mat, n//2);
        if n % 2 == 0:
            result = mul(tmp, tmp);
        else:
            a = [1, 1, 1, 0];
            result = mul(mul(tmp, tmp), mat);
    return result;


def mul(a, b):
    c = [(a[0] * b[0] + a[1] * b[2]) % 1000000007, (a[0] * b[1] + a[1] * b[3]) % 1000000007,
         (a[2] * b[0] + a[3] * b[2]) % 1000000007, (a[2] * b[1] + a[3] * b[3]) % 1000000007];
    return c;


# n = int(sys.stdin.readline().strip())
n = int(input());
mat = [1, 1, 1, 0];
fibo = mat_pow(mat, n-1);
print(fibo[0]); # Fn 즉, n번째 피보나치 수 출력

행렬 멱법을 이용한 피보나치 값 구하기

피보나치 수는 행렬 {{1,1},{1,0}} 의 멱수를 이용해서 구할 수 있다.
다시 말해서 행렬 멱법을 사용해서 구할 수 있다.

멱법(Exponentiation): 수학에서 한 수를 다른 수의 거듭제곱으로 표현하는 연산
멱수: 거듭제곱으로 이루어진 수. 밑과 지수를 이루어 한 번에 이르는 말

 

출처: https://zzonglove.tistory.com/32

즉. 위와 같은 수식이 성립한다는 것이다.

행렬은 역슬래쉬 방향 대각선(빨간색)에서 슬래쉬 방향 대각선(파란색)을 빼는 것으로 구할 수 있다.
따라서 위와 같이 계산할 수 있다.

Fm+n-1을 활용했을 때, 아래와 같은 식을 구할 수 있다.

출처: https://zzonglove.tistory.com/32

여기서 n = n + 1을 한다면, 다음과 같이 된다.

출처: https://zzonglove.tistory.com/32

(1)과 (2)에 m = n을 적용하면,
짝수와 홀수일 경우에 각각 피보나치 수를 구하는 공식이 만들어진다.

출처: https://zzonglove.tistory.com/32

그래서 이걸 코드에 대입해보면,

fibo = mat_pow([1, 1, 1, 0], n-1)로 n번재 피보나치 행렬을,
fibo[0]으로 Fn을 구할 수 있는 것이다.

(너무 어렵다...)