[백준] 24416번 알고리즘 수업 - 피보나치 수 1(python)

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

24416번: 알고리즘 수업 - 피보나치 수 1

 

1. 내가 작성한 코드

import sys

input = sys.stdin.readline

cnt1 = 1
cnt2 = 0

n = int(input().rstrip())

d = [0] * (n+1)

def fibo1(x): #재귀함수 이용
  global cnt1
  if x == 1 or x == 2:
    return 1
  else:
    cnt1+=1
    return fibo1(x-1) + fibo1(x-2)

def fibo2(x): #DP이용
  global cnt2
  d[1] = 1
  d[2] = 1

  for i in range(3,x+1):
    d[i] = d[i-1] + d[i-2]
    cnt2+=1
  
fibo1(n)
fibo2(n)
print(cnt1,end=' ')
print(cnt2)

시간 초과를 피하기 위해서 pypy3로 풀었다.

 

bfs, dfs 어느정도 감 잡았다 생각했는데 이번엔 dp,,,,,,,,,ㅠㅠ