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

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

1003번: 피보나치 함수

 

import sys
input = sys.stdin.readline

cases = int(input().strip())
numlist = [int(input().strip()) for _ in range(cases)]
lists = [0,1] + [0]*(cases-1)
for N in numlist:
    if N == 0:
        print(1, 0)
        continue
    lists = [0,1] + [0]*(N-1)
    for i in range(2, N+1):
        lists[i] = lists[i-1] + lists[i-2]
    print(lists[-2], lists[-1])

 

이번 2023 동계 알고리즘 멘토링에서 다이나믹 프로그래밍에 대해서는 마지막에 배워서 잘 기억이 안나지만 재귀로 짜는 거랑 for문으로 짜는 거랑 했을 때 재귀는 코테에서 대부분 깊이제한에 걸려서 for문으로 짜라고 했던게 기억이 났다. 

이번 문제도 피보나치에서 1이 나오는 개수는 전에꺼 2개를 합친거랑 같고 0은 n-1 의 1이 나오는 개수랑 같다는 거를 알아내고 그걸 이용해서 문제를 풀었다.