[백준 / Python] 1003번 피보나치 함수

문제

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

1003번: 피보나치 함수

---

코드

import sys

input = sys.stdin.readline

T = int(input())
data0 = [0] * 45
data1 = [0] * 45

data0[0] = 1
data1[0] = 0
data0[1] = 0
data1[1] = 1

for i in range(2, 42):
    data0[i] = data0[i - 1] + data0[i - 2]
    data1[i] = data1[i - 1] + data1[i - 2]

for _ in range(T):
    n = int(input())
    print(data0[n], data1[n])

 

---

풀이

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

 
다음은 이 문제에서 사용되는 피보나치 c언어 함수이다. 
이 문제는 n이 입력이 되었을때 fibonacci(n)이 fibonacci(0)과 fibonacci(1)을 호출을 각각 몇번하는지에 대한 문제이다. 
 

fibonacci를 f로 줄여서 설명하면,
위 표는 n에 따른 f(0), f(1)의 호출 횟수이다. 
자세히보면 규칙을 찾을 수 있다. 

 자세히 보면 n-1열의 값을 n-2열의 값을 더한 값이 n번째의 열의 값이다. 
위 패턴을 이용해 배열에 값을 미리 계산하고 입력값에 대해 출력을 하면 되는 문제이다. 

---

위 패턴은 c언어 함수에서도 힌트를 알 수 있다. 

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

위 함수를 보면 n이 0과 1이 아니라면 f(n - 1)과 f(n - 2)를 호출한다. 
이 부분에서 위 패턴을 유추할 수 있다.