[baekjoon]백준 1003번 : 피보나치 함수 (by python 파이썬)

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

1003번: 피보나치 함수

 

정답 code

t = int(input())

for _ in range(t):
    f0 = [1,0]
    f1 = [0,1]
    n = int(input())
    if n>1:
        for i in range(n-1):
            f0.append(f1[-1])
            f1.append(f0[-2]+f1[-1])
            print(f0,f1)
    print(f0[n],f1[n])

 

 

시간초과 code

import sys
input = sys.stdin.readline

def fibonacci(n):
    global zcount, ocount
    if n==0:
        # print(0)
        zcount += 1
        return 0
        
    elif n == 1:
        # print(1)
        ocount += 1
        return 1
    else:
        return fibonacci(n-1)+fibonacci(n-2)

t = int(input())

for _ in range(t):
    zcount = 0
    ocount = 0
    fibonacci(int(input()))
    print(zcount,ocount)

처음 작성한 코드는 문제의 피보나치 함수를 그대로 활용해 해당 값을 불러올때마다

전역변수로 설정한 변수에 카운팅을 해주는 방식으로 문제를 풀었는데 시간초과가 뜨고 말았다.

줄일 방법을 생각해 봤지만 도통 떠오르지 않아 구글링을 해본결과 규칙을 이용해 해결하는 방법을 이용 했다.

 

solution

1. 0과 1일때의 경우를 대입하고

2. 1보다 큰경우에 대해 입력된 수-1 까지 탐색한다.

3. 규칙 = 0이 출력되는 경우는 전 1이 출력되는 값

             1이 출력되는 경우는 전 0출력 + 1

4. 각 저장 리스트에 마지막 값 출력