Baekjoon1003_피보나치 함수

문제

풀이

DP문제는 풀이 방식을 떠올리기가 너무 어려운것 같다.
이 문제는 시간제한이 있어 문제에 나와있는 소스코드를 그대로 사용하려고 하면 시간초과가 난다.(본인이 그렇게 날로먹으려다 실패했다.) 시간을 최대한 줄이기위해서 우선 구해야하는 것이 무엇인지 먼저 보았다.
재귀적인 방법으로 피보나치 수열을 구할때 n번째 수는 0과 1을 몇번 호출해야 하는가를 구하는 것이 문제에서 원하는 답이다. 즉, f(n)을 재귀적인 방법으로 구할때 f(1)과 f(0)은 총 몇번 호출되는가 이걸 구하면 된다.

피보나치 수열의 n번째 수는 n-2번째 수와 n-1 번째 수의 합이므로 0이 나오는 횟수와 1이 나오는 횟수도 n-2번째와 n-1번째의 경우를 합치면 된다.

0이 나오는 횟수와 1이 나오는 횟수를 배열로 만들어보면 0이 나오는 횟수(zero_list) = [1,0], 1이 나오는 횟수(one_list) = [0,1] 이다. 인덱스 n은 피보나치 수열의 n번째 횟수이고 각 값들은 호출되는 횟수이다. f(2) = f(1) + f(0) 이므로 각각의 리스트는 [1,0,1], [0,1,1]이 된다. 이와 같은 방법을 반복하면 n번째 피보나치 수열의 수는 f(0),f(1)이 zero_list(n),one_list(n) 만큼 호출된다.

풀이코드

t = int(input())

for _ in range(t):
    n = int(input())
    z_list = [1,0,1]
    o_list = [0,1,1]

    length = len(z_list)

    if n >= length:
        for i in range(length,n+1):
            z_list.append(z_list[i-2] + z_list[i-1])
            o_list.append(o_list[i-2] + o_list[i-1])
    print(z_list[n],o_list[n])