[백준] 1003번: 피보나치 함수 (다이나믹 프로그래밍)

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

1003번: 피보나치 함수

 

이 문제는 규칙성을 이용하는 DP 문제이다.

우선 그림을 한 번 그려보자.

N에 따라서 0과 1이 어떻게 되는지 보자.

 

그림판으로 그려서 삐뚤삐뚤하다..ㅠ

이 규칙성을 가지고 DP를 사용하여 구현하면 풀이는 다음과 같다.

 

t = int(input())

for _ in range(t):
    cnt_0 = [1, 0]
    cnt_1 = [0, 1]
    n = int(input())
    if n > 1:
        for i in range(n - 1):
            cnt_0.append(cnt_1[-1])
            cnt_1.append(cnt_0[-2] + cnt_1[-1])

    print(cnt_0[n], cnt_1[n])