알고리즘 - Python / 백준 - 1003번 : 피보나치 함수

1003번: 피보나치 함수 (acmicpc.net)

1003번: 피보나치 함수

 

---

풀이

• DP 문제 이므로 점화식을 먼저 찾는다
• 문제에 친절하게 모든 경우에 대해 점화식을 설명해두었다
• 구한 점화식을 통해 모든 DP 배열을 채우고 원하는 답을 출력하면 된다

 

import sys

stack = [[0 for i in range(2)] for j in range(41)]
n = int(sys.stdin.readline())
stack[0][0] = 1
stack[1][1] = 1
for i in range(2,41):
  stack[i][0] = stack[i-1][0] + stack[i-2][0]
  stack[i][1] = stack[i-1][1] + stack[i-2][1]

for _ in range(n):
  m = int(sys.stdin.readline())
  print(stack[m][0], end=" ")
  print(stack[m][1], end="\n")

---