백준 1003 파이썬 - 피보나치 함수 - 동적 계획법

백준 1003 파이썬

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

1003번: 피보나치 함수

재귀를 통한 피보나치를 구하고 0과 1까지 내려갔을 때 0과 1을 출력해주는 함수가 주어진다.

이때 0과 1을 출력한 횟수를 구하는 알고리즘 문제이다.

 

피보나치 수열을 재귀로 주로 구현하는데... 동적 계획법으로도 충분히 가능하다. 특히 이번 문제에서는 출력되는 결과를 구하는 것이기 때문에.... 숫자 N에대해서 N-1과 N-2 번째에 출력한 0과 1의 수를 합산하면 결과를 얻을 수 있다.

 

 

Python 풀이

import sys
read = sys.stdin.readline

cache = {0: [1,0], 1:[0,1]}
for i in range(2, 41):
    cache[i] = [cache[i-2][j] + cache[i-1][j] for j in range(2)]

T = int(read())
for _ in range(T):
    print(' '.join(map(str, cache[int(read())])))

• 초기 값으로 지정할 0과 1일 때 출력하는 횟수를 딕셔너리에 담는다.
• N은 최대 40까지라는 제한이 있어 그냥 미리 결과를 만들어 놓는다.