99클럽 코테 스터디 18일차 TIL Boj 1003. 피보나치 함수

Approach

• 처음에 그냥 피보나치 문제인 줄 알고 dfs로 풀어버렸는데 시간초과가 났다.
• 하나의 dp 배열로 기록해도 됐지만, 오랜만에 메모이제이션 문제를 풀다 보니 좀 더 직관적으로 풀기 위해 zero와 one 두 개의 배열을 선언했다.
• 나머지는 알다시피 dp로 바텀업 방식을 활용하여 문제를 해결하였다.

---

Solution 💡

import sys

def fibo(n):

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

    for i in range(2, n+1):
        zero[i] = zero[i-1] + zero[i-2]
        one[i] = one[i-1] + one[i-2]

T = int(sys.stdin.readline().strip())

for _ in range(T):
    N = int(sys.stdin.readline().strip())
    zero = [0] * (N+1)
    one = [0] * (N+1)
    if N == 0:
        print(1, 0)
    elif N == 1:
        print(0, 1)
    else:
        fibo(N)
        print(zero[N], one[N])