백준 1003 - 피보나치 함수

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

1003번: 피보나치 함수

DP 문제다. 넷플릭스 드라마 말고, Dynamic Programming(동적 프로그래밍) 문제. 악명 높은 테마다.

 

동적 프로그래밍이란 건 다른 말로 메모이제이션(Memoization)이라고도 하는데, 내가 이전에 계산해 놓은 값들을 컴퓨터 공간 어딘가에 저장해 둔 뒤, 해당 계산을 다시 반복해야 할 일이 있을 때 계산을 다시 반복할 필요 없이 이전에 적어 놓은 값을 가져와서 계산에 활용하는 방식을 말한다.

 

이런 유형을 가장 잘 설명해주는 예제가 바로 피보나치 함수다.

피보나치 수는 f(0)=0, f(1)=1일 때, f(n) = f(n-1)+f(n-2)의 형태로 된 수열을 말한다.

f(3)을 구하기 위해서는 f(2)를 구해야 하고, f(2)는 f(1)과 f(0)으로 구성되어 있다.

f(4)를 구하기 위해서는 f(3)과 f(2)를 구해야 하고, f(3)과 f(2)는 위에서 계산했으니까 그 값들을 어딘가에 저장해뒀다면 가져올 수 있을 것이다. f(5), f(6)... 모두 마찬가지다.

 

이렇게 하지 않으면 각 계산을 할 때마다 모두 다 새로 계산을 해야 하기 때문에 시간이 엄청나게 많이 소요된다. f(9999)를 일일이 계산하려면 얼마나 많은 시간이 걸릴까 ㅋㅋ

 

import sys
input = sys.stdin.readline

n = int(input())
fibo_0 = [0]*41
fibo_0[0] = 1
fibo_1 = [0]*41
fibo_1[1] = 1
for x in range(2, 41):
    if fibo_0[x] == 0:
        fibo_0[x] = fibo_0[x-1]+fibo_0[x-2]
    if fibo_1[x] == 0:
        fibo_1[x] = fibo_1[x-1]+fibo_1[x-2]

for i in range(n):
    case = int(input())
    print(f'{fibo_0[case]} {fibo_1[case]}')

테스트하는 값이 40까지기 때문에 fibo_0(0이 등장하는 횟수의 array), fibo_1(1이 등장하는 횟수의 array)를 생성하고, f(0)은 0이 1번 등장하고 1은 등장하지 않으니 fibo_0[0] = 1로 설정한다.

f(1)은 0이 0번 등장하고 1은 1번 등장하니 fibo_1[1] = 1로 설정한다.

이후 반복문으로

fibo_0 array와 fibo_1 array의 값을 순차적으로 채운다.

 

이후 테스트 케이스가 들어왔을 때 케이스 값을 배열의 인덱스 값으로 해서 호출한다.