백준) 1003번 피보나치 함수

문제

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

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);
    }
}

입력 & 출력

• 입력 : 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

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

풀이

예시입력을 잘 살펴보면 한가지 규칙을 얻을 수 있다. 입력 0을 제외하고 1부터 보면,
각 출력 횟수는 피보나치 수열을 따른다는 것을 알 수 있다.

• 0 : N-1번째 피보나치 수열의 값
• 1 : N번째 피보나치 수열의 값

따라서 다음과 같이 풀이한다.

import sys
answer = []
def fib(n):
    list = [0,1]
    while len(list)<n+1:
        list.append(list[-1]+list[-2])
    if n == 0:
        return 0,1
    else:
        return list[-1],list[-2]

T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())
    f1,f0=fib(N)
    answer.append((f0,f1))

for a,b in answer:
    print(a,b)