<백준 문제풀이: 1003번> 피보나치 함수

저번주에 풀지 못해서 잠시 안풀고 있다가 1주일 뒤인 오늘 돌아와서 다시 생각해보았다.

n 값	0	1	2	3	4
0	1	0	1	1	2
1	0	1	1	2	3

그래서 이번에는 위의 테이블을 만들어 보았다. 보면 더 확실하게 보이는 것이, n값이 0, 1, 2는 하나씩 찾아보아야 하지만, 3, 4일때 0과 1이 나오는 횟수는 그 전의 두 숫자의 횟수에 더해지는 것이다.

따라서 다음과 같이 한번 코드를 짜봤다:

import sys

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

num_0 = [1, 0, 1]
num_1 = [0, 1, 1]

for i in range(T):
    N = int(sys.stdin.readline())
    if len(num_0) <= N:
        for j in range(len(num_0), N+1):
            num_0.append(num_0[j-2]+num_0[j-1])
            num_1.append(num_1[j-2]+num_1[j-1])
    print(str(num_0[N]) + ' ' + str(num_1[N]))
    

num_0 과 num_1이라는 list를 만들어 거기에 n=0, 1, 2일때의 값을 집어넣어준다.

이후, 만약 N보다 len(num_0)이 더 짧다면, 짧은 만큼 (range(len(num_0), N+1) 피보나치 수열을 연장시켜 num_0 과 num_1을 연장시켜준다. 마지막에는 원하는 방식의 출력을 해준다.