#2_ 피보나치 함수(백준 1003번, 파이썬 풀이)

문제

다음 소스는 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);
    }
}

fibonacci(3) 을 호출하면 다음과 같은 일이 일어난다.

fibonacci(3) 은 fibonacci(2) 와 fibonacci(1) (첫 번째 호출)을 호출한다.

fibonacci(2) 는 fibonacci(1) (두 번째 호출)과 fibonacci(0) 을 호출한다.

두 번째 호출한 fibonacci(1) 은 1을 출력하고 1을 리턴한다.

fibonacci(0) 은 0을 출력하고, 0을 리턴한다.

fibonacci(2) 는 fibonacci(1) 과 fibonacci(0) 의 결과를 얻고, 1을 리턴한다.

첫 번째 호출한 fibonacci(1) 은 1을 출력하고, 1을 리턴한다.

fibonacci(3) 은 fibonacci(2) 와 fibonacci(1) 의 결과를 얻고, 2를 리턴한다.

이 때, 1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N) 을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어 있다.

첫째 줄에 N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력 :

3

0

1

3

예제 출력 :

1 0

0 1

1 2

---

쉽게 말해서, 피보나치 수열 함수 중 fibonacci(1)과 fibonacci(0) 이 몇 번 호출되는지 구하는 문제입니다.

먼저 최종 정답코드는 아래와 같습니다.

a = int(input())
 
zero = [1,0,1]
one = [0,1,1]
 
def cal(num):
    length = len(zero)
    if length <= num:
        for i in range(length,num+1):
            zero.append(zero[i-1]+zero[i-2])
            one.append(one[i-1]+one[i-2])
    print("%d %d"%(zero[num],one[num]))
 
for i in range(a):
    k = int(input())
    cal(k)

fibonacci(N)을 호출했을 때 fibonacci(1)과 fibonacci(0)이 몇번 호출되었는지 알기 위해 아래와 같은 표를 작성해 보았습니다.

N 값	0	1	2	3	4	5	6	7	8
0 호출회수	1	0	1	1	2	3	5	8	13
1 호출회수	0	1	1	2	3	5	8	13	21

위의 표를 보고 규칙성을 찾으셨나요?

아직 애매하다면 조금 더 자세히 살펴볼게요.

fibonacci(2) = fibonacci(1) + fibonacci(0) 입니다.

그리고, fibonacci(3) = fibonacci(2) + fibonacci(1) 입니다.

그럼, fibonacci(3) 에서 0과 1의 호출 회수는, fibonacci(2)와 fibonacci(1)의 0과 1의 호출 회수를 각각 더하면 되겠죠?

이를 식으로 써본다면,

입력 값 3에 대한 0 호출회수 = (입력 값 2에 대한 0 호출회수) + (입력 값 1에 대한 0 호출회수)

입력 값 3에 대한 1 호출회수 = (입력 값 2에 대한 1 호출회수) + (입력 값 1에 대한 1 호출회수)

그럼 입력 값 4일때는 어떨까요?

fibonacci(4) = fibonacci(3) + fibonacci(2) 이므로,

입력 값 4에 대한 0 호출회수 = (입력 값 3에 대한 0 호출회수) + (입력 값 2에 대한 0 호출회수)

입력 값 4에 대한 1 호출회수 = (입력 값 3에 대한 1 호출회수) + (입력 값 2에 대한 1 호출회수)

입니다.

이제 뭔가 보이지 않나요?

호출회수 또한 피보나치 수열을 따르고 있습니다.

이러한 개념을 바탕으로 코드를 구현하면 아래와 같습니다.

먼저 최종 정답으로 통과한 코드는 아래와 같습니다.

a = int(input())
 
zero = [1,0,1]
one = [0,1,1]
 
def cal(num):
    length = len(zero)
    if length <= num:
        for i in range(length,num+1):
            zero.append(zero[i-1]+zero[i-2])
            one.append(one[i-1]+one[i-2])
    print("%d %d"%(zero[num],one[num]))
 
for i in range(a):
    k = int(input())
    cal(k)

먼저 처음에 몇번 계산을 할 것인지, 테스트 케이스의 개수를 a로 받습니다.

그리고 6번 라인부터 12번 라인까지가 각 숫자에 대한 0과 1의 호출 횟수를 출력하는 함수입니다.

위에서 알아본 바와 같이 피보나치 수열식으로 호출 횟수를 구하여 출력하였습니다.

이를 위한 초기값은 3번라인과 4번라인에 있습니다.

궁금하신 점이나 오류가 나는 점은 언제든 댓글을 달아주세요 :)