백준 1003 파이썬 | 피보나치 함수

코드

from sys import stdin
input = stdin.readline

T = int(input())
fibo = [[1, 0], [0, 1]]

for i in range(2, 41):
    fibo.append([fibo[i-1][0] + fibo[i-2][0], fibo[i-1][1] + fibo[i-2][1]])

for _ in range(T):
    n = int(input())

    print(fibo[n][0], fibo[n][1])

설명

피보나치 수열을 재귀 함수를 이용하여 만들었을 때, fibonacci(N)에서 0과 1이 몇 번 출력되는지 구하는 프로그램이다.

 

피보나치 수열은 대표적인 dp의 예이기 때문에 동적프로그래밍을 이용하여 문제를 풀었다. 피보나치 수열의 특성상 n번째 수열의 값은 n-1, n-2 의 값에 의존하고 있기 때문에 동적프로그래밍을 사용할 수 있다. 재귀 함수로 피보나치 수열을 구현 하면 계속해서 fibonacci(0)과 fibonacci(1)를 실행시키기 때문에 dp를 구현 할 때에도 n-1 번째와 n-2 번째에 0과 1을 부르는 횟수를 각각 더해주면 된다.

 

N의 값의 범위가 0 - 40 으로 그리 크지 않기 때문에 테스트 케이스를 입력 받기 전에 모든 경우를 dp를 이용하여 리스트에 저장하였다. 0과 1이 각각 몇 번 출력되는지 알아야 하니 2차원 배열을 이용하여 각각 저장해 주었다.

 

그리고나서 테스트 케이스에 대하여 n이 주어졌을 때 리스트에서 그 값을 출력해 주면 된다.

 

메모리: 29200KB

시간: 80ms

문제

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

1003번: 피보나치 함수