[ BOJ / 파이썬 ] 1003. 피보나치 함수

너무 흔한 재귀 함수 문제인 줄 알았는데 

시간제한이 빡빡해서 최대값 40을 찍어보니 아 역시..

어차피 바텀업 느낌으로 가는 문제이고 하위 문제를 상위에서 갖다 쓰는거라 중복을 최소화할 방법을 찾고자 했다.

 

그냥그냥 DP로 풀 수 있었다! 

피보나치 자체가 n >= 2 부터 fibo(n) = fibo(n-1)+fibo(n-2)의 식을 갖고, 3까지 찍어보니 정말 그 아래 값들의 0과 1등장횟수를 각각 더해주면 된다.

 

처음에는 피보나치 함수 자체에서 해당 테이블을 갱신하려고 했으나,

일단 일반식을 얻어낸 이상 그냥 dp 테이블 정의하고 for문 돌려 착착 순서대로 채우면 되는거였다. 

 

tc = int(input())
for testCase in range(tc):
  result = [0, 0]
  n = int(input())
  dp = [[0, 0] for _ in range(n+1)]
  dp[0] = [1, 0]
  if n > 0:
    dp[1] = [0, 1]
    for i in range(2, n+1):
      dp[i][0] = dp[i-1][0] + dp[i-2][0]
      dp[i][1] = dp[i-1][1] + dp[i-2][1]
    
  print(*dp[n])

 

 

역시 학습은 반복! 반복은 학습!