[백준] 1003 - 피보나치 함수 (python)

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

1003번: 피보나치 함수

문제

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

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이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력 1

3
0
1
3

예제 출력 1

1 0
0 1
1 2

예제 입력 2

2
6
22

예제 출력 2

5 8
10946 17711

풀이

import sys
input=sys.stdin.readline
for i in range(int(input())):
    n=int(input())
    if n==0:
        tupC=(1,0)
    elif n==1 :
        tupC=(0,1)
    else :
        tupA=(1,0)
        tupB=(0,1)
    for i in range(n-1):
        tupC=tuple(sum(j) for j in zip(tupA, tupB))
        tupA=tupB
        tupB=tupC
    print(*tupC)

f(0) = (1,0)

f(1) = (0,1)

f(2) = (1,1)

f(3) = (1,2)

f(4) = (2,3)

 

즉, f(2)=f(1)+f(0), f(3)=f(2)+f(1), f(4)=f(3)+f(2) 이 과정만 알면 무난하게 풀 수 있었던것 같다.

f(1)인 경우와 f(0)인 경우만 if를 이용하여 값을 따로 할당하였고 아닌결우엔 반복문을 이용하여 값을 계속 더하는 식으로 구하였음.

 

다이나믹 프로그래밍은 경험이 없어 구글링을 통해 많은 답을 비교하였는데 함수선언을 통한 재귀로 푸는듯 하였다.

내코드가 올바른 풀이인지는 사실 잘 모르겠지만 여튼 통과는 됐다.

아무래도 좋은 코드는 아닌듯