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

문제 )

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

1003번: 피보나치 함수

 

[ 풀이 ]

문제를 읽어보고 그냥 재귀함수를 사용해서 문제를 풀되 fib(0)과 fib(1)이 얼마나 호출되는지 알아내게끔 코드를 변경하라는 건줄 알았다. 

문제를 풀고 제출해보니 시간초과가 되어버렸다. 

그래서 시간초과를 하지 않는 새로운 방법으로 문제를 풀어보았다.

바로 0과 1 호출 횟수에 대한 List를 만들어 Dynamic Programming으로 문제를 푸는 것이다

예를 들어 , fib(3)= fib(2)+fib(1) = fib(0) + fib(1) + fib(1) 로 fib(1)은 2번 fib(0)은 1번 호출되는 것을 볼수 있다. 

 

- 동적 프로그래밍 ( Dynamic Programming) 이란?

✔  입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용해 큰 크기의 부분 문제들을 해결하여 최종적인 solution을 해결하는 Algorithm
✔ Bottom - up 

 

 

- python code 

def fibonacci(n):
    count0=[1,0] # 0을 사용하는 횟수 list
    count1=[0,1] # 1을 사용하는 횟수 list
    for i in range(2,n+1):
        count0.append(count0[i-1]+count0[i-2])
        count1.append(count1[i-1]+count1[i-2])
    return count0[n], count1[n]

T=int(input())
for i in range(T):
    N=int(input())
    sc0,sc1=fibonacci(N)
    print(sc0,sc1)