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

백준 1003번 문제는 피보나치 함수 문제이다.

피보나치 수열은 동적계획법(Dynamic Programming,DP)의 예제로 유명하다.

 

0과 1이 몇 번 출력 되는 횟수는 fibonacci(0)과 fibonacci(1)이 되는 횟수를 구하면 되는 것이다.

문제를 자세히 보니 n이 1보다 클 경우 fibonacci(0)과 fibonacci(1)이 되는 횟수가 각각 피보나치 수열을 띄고 있었다.

• fibonacci(0)이 되는 횟수 : fibonacci(n-1)
• fibonacci(1)이 되는 횟수 : fibonacci(n)

즉, n이 2이상일 경우에 동적 계획법을 사용하여 피보나치 함수를 만든 후에 각각 그 값을 반환해 주면 되는 것이었다!!

 

※주의※

출력 시, string으로 출력해야 됩니다.

 

a=[0,1]
def fib(n):
    global a
    if(n>len(a)-1):
        for i in range(len(a),n+1):
            a.append(a[i-1]+a[i-2])
    return a[n]

def count_fib(t):
    for i in range(t):
        x=int(input())
        if(x==0):
            print("1 0")
        elif(x==1):
            print("0 1")
        else:
            print(f"{fib(x-1)} {fib(x)}")

cin = int(input())
count_fib(cin)