[백준] 1003 피보나치 함수 (보텀업)

# 백준 1003 피보나치 함수
d = [0] * 10001
t = int(input())

for i in range(t):
    d[0] = 1, 0
    d[1] = 0, 1
    n = int(input())
    for i in range(2, n + 1):
        d[i] = d[i-1][0] + d[i-2][0], d[i-1][1] + d[i-2][1]
    print(d[n][0], d[n][1])

재귀 말고 반복문을 사용했다

문제를 풀기 전에 함수가 호출되는 과정을 그림으로 그려보았다

0이 출력되는 횟수와 1이 출력되는 횟수를 튜플을 이용해 배열에 넣었다

 

보텀업 방식으로

f(3) = f(2) + f(1) = (f(1) + f(0)) + f(1) -> 트리로 그렸음

f(1)에는 0이 0번 1이 1번

f(0)에는 0이 1번 1이 0번

 

구하고 싶은 값이 d[3]라면?

d[0] = 1, 0

d[1] = 0, 1

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

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

 

이런식으로 출력되게 하였다