python 백준1003 피보나치 함수(BOJ1003)

문제링크 : https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

역시 dp하면 피보나치구나 싶다.

dp알고리즘 분류를 보면 피보나치가 엄청 많이 나오는데 아주 피보나치의 단물의 단물까지 쪽~쪽~ 빨아 먹을셈인가보다

근데 난 그 단물 맛좀 보고싶은데 참 쉽지않다

그!

렇!

지!

만!

이번엔 그 단물 맛좀 봤다

피보나치함수를 재귀호출하면 최종적으로 리턴 조건이 0과 1일때인데 주어지는 수가 0과 1을 몇번을 호출하는지 카운트하는 문제였다

이게 무슨일이람 보자마자 바로 이거다! 싶어서 제출했는데

띵~동 어림도없다 이놈아

뭐야 예제로 주어진 테스트케이스도 다 맞는데 뭐지??

알고봤더니 출력조건을 지키지 않아서였다..

그래서 수정후 코드

import sys

input = sys.stdin.readline

#테스트케이스
t = int(input())

dp = [[0,0] for _ in range(41)]
dp[0] = [1, 0]
dp[1] = [0, 1]

for _ in range(t):
  #입력
  n = int(input())
  #dp테이블에서 n까지의 값을 구한다
  for i in range(2, n+1):
    dp[i] = (dp[i-1][0]+dp[i-2][0], dp[i-1][1]+dp[i-2][1])
  #출력
  print(f'{dp[n][0]} {dp[n][1]}')

이로 제출해서 통과했다!

그런데 테스트케이스수만큼 반복문을 돌면서 매번 입력받는 수를 계산하는게 빠를까?

아니면 처음에 40까지 다 계산해두고 입력받는 수에 따라 값만 주는게 빠를게 궁금해서 해봤다

import sys

input = sys.stdin.readline

#테스트케이스
t = int(input())

dp = [[0,0] for _ in range(41)]
dp[0] = [1, 0]
dp[1] = [0, 1]

#미리 숫자범위까지 계산해놓기
for i in range(2, 41):
    dp[i] = (dp[i-1][0]+dp[i-2][0], dp[i-1][1]+dp[i-2][1])

for _ in range(t):
  #입력
  n = int(input())
  #출력
  print(f'{dp[n][0]} {dp[n][1]}')

이렇게 해봣는데

별차이 읎다

그래도 달다 끗.