알고리즘

• DP
• bottom-up
• 메모이제이션

설명

• 피보나치 수를 재귀 함수로 구현했을 때 fibo(0), fibo(1) 함수가 몇 번 호출되는지 카운트 하는 문제
• 재귀 함수에서 그대로 카운트할 경우 시간 초과
• bottom-up 방식으로 중복 호출을 방지

구현 방법

• n+1 길이의 리스트 초기화
• 2부터 n까지 돌면서
• (i번째 0 호출 횟수) = (i-1번째 0 호출 횟수) + (i-2번째 0 호출 횟수)
• (i번째 1 호출 횟수) = (i-1번째 1 호출 횟수) + (i-2번째 1 호출 횟수)

링크

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

코드

def init():
    n = int(input())
    fibo = [[0, 0] for _ in range(n+1)]
    if len(fibo) > 0: fibo[0] = [1, 0]
    if len(fibo) > 1: fibo[1] = [0, 1]
    return n, fibo


tc = int(input())
for _ in range(tc):
    n, fibo = init()
    if n == 0:
        print(1, 0)
    elif n == 1:
        print(0, 1)
    else:
        for i in range(2, n+1):
            fibo[i][0] = fibo[i-1][0] + fibo[i-2][0]
            fibo[i][1] = fibo[i-1][1] + fibo[i-2][1]
        print(fibo[n][0], fibo[n][1])