[백준 1003번 문제] 피보나치 함수

이 문제는 피보나치 함수를 이용해서 계산을 할 때 0과 1을 몇번 리턴하는지 카운트하는 문제이다.

 

 

처음에는 단순히 피보나치 함수를 만들고 그 안에서 0과 1을 카운트 하도록 구현하였다.

def fibo(n):
    if n == 0:
        # print("0")
        global cnt_zero
        cnt_zero += 1
        return 0
    elif n == 1:
        # print("1")
        global cnt_one
        cnt_one += 1
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

cnt_zero = 0
cnt_one = 0
num = int(input(""))

for i in range(num):
    n = int(input(""))
    fibo(n)
    print(cnt_zero, cnt_one)
    cnt_zero = 0
    cnt_one = 0

위에 처럼 코딩을 했더니 시간초과 에러가 떠서 다른 방식을 생각해 보았다.

 

def fibo(n):
    if len(zero) <= n:
        for i in range(len(zero), n+1):
            zero.append(zero[i-1] + zero[i-2])
            one.append(one[i-1] + one[i-2])
    print(zero[n], one[n])

zero = [1,0,1]
one = [0,1,1]
num = int(input())

for i in range(num):
    n = int(input(""))
    fibo(n)

배열을 이용해서 0과 1이 호출된 횟수를 적은 배열을 선언한 뒤에 for문을 이용해서 계산한 횟수를 배열에 append하는 방식으로 구현하였더니 성공했다. 코테 문제를 풀 때 푸는 것도 중요하지만 시간초과가 되지 않도록 구현하는것도 중요한 문제인거 같다.