[python] 백준 1003 - 피보나치 함수

출처 : 백준, https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

 

먼저, 생각해야 할 부분

 

1. 전형적인 DP 문제인데 해보면 규칙이 나오는 경우.........

 

 

---

 

풀이

 

T = int(input())

for _ in range(T):
  n = int(input())
  dp = [[0 for _ in range(n+1)] for _ in range(2)]

  try:
    dp[0][0] = 1
    dp[1][1] = 1
  except:
    pass

  for i in range(2, n+1):
    dp[0][i] = dp[0][i-1] + dp[0][i-2]
    dp[1][i] = dp[1][i-1] + dp[1][i-2]

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

 

---

시간 복잡도

O(T*N).......으로 표현해도 될까?

 

알게 된 점

 

-

고찰

 

DP 문제를 접근할 때, 규칙이 나올 것 같으면 해보고,

해봤는데 안나오면 바로 전 단계를 생각하자.

 

Github

백준 1003 - 피보나치 함수