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

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

 

입력 :

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

 

출력 :

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

 

 

풀이)

처음에 풀었던 풀이. 

일반적인 피보나치 함수를 만드는 재귀함수를 그대로 가져다가 cnt의 수만 늘렸다.

당연히 시간초과. 시간제한이 0.25초이기 때문에 시간을 더 줄일 필요가 있었다.

def fibo(n):
    global cnt_0
    global cnt_1
    if n == 0:
        cnt_0 += 1
        return 0
    elif n == 1:
        cnt_1 += 1
        return 1
    else:
        return fibo(n-1) + fibo(n-2)
 
n = int(input())
for i in range(n):
    cnt_0 = 0
    cnt_1 = 0
    m = int(input())
    fibo(m)
    print(cnt_0, cnt_1)

그렇게 해결방안? 으로 생각한게, 입력값 중 최댓값을 구한 뒤, 그 최대값을 기준으로 

피보나치 함수의 리스트를 미리 만들어 놓고 그 뒤에 나머지 값들을 출력하는 방식이다.

li = [[1, 0], [0, 1]]
 
nums = []
n = int(input())
for i in range(n):
    m = int(input())
    nums.append(m)
 
while max(nums) != li.index(li[-1]):
    li.append([li[-2][0] + li[-1][0], li[-2][1] + li[-1][1]])
 
for i in nums:
    print(*li[i])

---

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

1003번: 피보나치 함수