[BOJ] 1003 피보나치 함수 - python

1003번: 피보나치 함수 (acmicpc.net)

1003번: 피보나치 함수

 

일반적인 피보나치 수열 문제의 간단한 변형 문제라고 생각된다.

피보나치 함수에서 0 혹은 1까지 방문하는 횟수를 세는 문제이다.

 

처음에는 평소와 같이 재귀를 이용하여 풀었더니 시간 초과가 발생하였다.

각 숫자 별로 0과 1의 수를 리스트 형태로 전부 저장한 뒤, 값을 꺼내왔다.

 

import sys

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

for _ in range(T):
    N = int(sys.stdin.readline())
    dp = [[0,0] for i in range(N+1)]

    if N == 0:
        print("1 0")
        continue
    elif N == 1:
        print("0 1")
        continue
    
    dp[0] = [1,0]
    dp[1] = [0,1]

    for j in range(N+1)[2:]:
        # dp[3] = [dp[2][0]+dp[1][0], dp[2][1]+dp[1][1]]
        dp[j] = [dp[j-1][k] + dp[j-2][k] for k in range(2)]

    print(dp[N][0], dp[N][1])