[#알고리즘/Dynamic Programming/[백준]1003번:피보나치 수열(python)]

Question

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

Solution

DP 테이블의 각 원소값 d[n]이 0을 출력하는 횟수와 1을 출력하는 횟수를 저장하는 2차원 리스트를 생성한다. 그 후 앞서 배운 피보나치 수열을 Bottom-up의 반복문으로 구현한다. d[n]은 각각 0과 1의 횟수를 저장하고 있다. 과정은 아래와 같이 진행된다.

d[0]은 [1,0]
d[1]은 [0,1]
d[2]는 [1,1]

d[3] = d[2] + d[1] -> d[3]은 [0+1, 1+0] = [1, 2]
d[4] = d[3] + d[2] -> d[4]는 [1+1, 2+1] = [2, 3]
....

Code

import sys
input = sys.stdin.readline

T = int(input())
N = [int(input()) for _ in range(T)]

d = [[0] * 2 for _ in range(41)]
d[0] = [1, 0]
d[1] = [0, 1]
d[2] = [1, 1]

def fibo(x) :
    for i in range(3, x + 1) : 
        d[i][0] = d[i-1][0] + d[i-2][0]
        d[i][1] = d[i-1][1] + d[i-2][1]
    return d[x]
    
for x in N :
    fibo(x)
    print(d[x][0], d[x][1])