백준 1003 피보나치 함수 - Python

출처 :

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

1003번: 피보나치 함수

풀이 :

t = int(input())

zero = [1,0,1]
one = [0,1,1]

def fibo(num):
    length = len(zero)
    if num >= length:
        for i in range(length, num+1):
            zero.append(zero[i-2]+zero[i-1])
            one.append(one[i-2]+one[i-1])
    print(f'{zero[num]} {one[num]}')

for _ in range(t):
    fibo(int(input()))

문제 부터 보면 피보나치 수열을 푸는 과정에서 결론적으로 0과 1의 조합이 몇 개 이냐를 물어보는 문제이다.

 

fibo(0) = 0

fibo(1) = 1

fibo(2) = fibo(1) + fibo(0) = 1 [1,1]

fibo(3) = fibo(2) +fibo(1) = [1,1] + [0,1] = [1,2]

fibo(4) = fibo(3) +fibo(2) = [1,2]+[1,1] = [2,3]

 이런 과정으로 답을 도출 할 수 있다.

 

하지만 이를 코드로 fibo(2) + fibo(3) = [1,1,1,2] 이런 결과가 나와서 굉장히 곤란해지는 상황이 발생한다.

 

따라서 나는 0의 개수를 [1,0,1,1,2...] 이런 형태의 피보나치로 진행 시킬거고 1도 마찬가지로 진행 하겠다.

 

그런 다음 다이나믹 프로그래밍의 정의 : 하나의 문제는 단 한 번 풀고 넘어간다. 를 적용해서

 

배열된 길이를 센 다음 그 길이에서부터 우리가 구하는 값까지 계산하게 설정했다.