[백준/ 파이썬] 1003 피보나치 함수

#문제링크

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

1003번: 피보나치 함수

#나의풀이

import sys

if __name__ == '__main__':
    T = int(sys.stdin.readline())

    for _ in range(T):
        number = int(sys.stdin.readline())
        fibo = [[1,0],[0,1],[1,1]]

        for i in range(3, number+1):
            fibo.append([fibo[i-1][1],fibo[i-1][0]+fibo[i-1][1]])
        print(fibo[number][0], fibo[number][1])

#해설

문제에서 주어진 피보나치 함수를 사용하면 시간초과가 발생한다. 규칙을 찾아야하는데

0부터 9까지 피보나치를 돌려 0과 1의 개수를 파악해보면 0과 1은 [1, 0] [0, 1] 고정값이고

0은 이전값 1의개수 1은 이전값 0의개수 + 1의개수인걸 확인할 수 있다.