백준 24416번 바로가기

나의 풀이

a_count = 1
b_count = 1

def fibo(n):
  global a_count
  if n==1 or n==2:
    return 1
  else:
    a_count += 1
    return fibo(n-1) + fibo(n-2)

def fibonacci(n):
  global b_count
  f = [1,1] + [0]*(n)
  for i in range(3, n):
    f[i] = f[i-1] + f[i-2]
    b_count += 1
  return f[n]

fibo(n:=int(input()))
fibonacci(n)

print(a_count, b_count)

CODE REVIEW

  1. 재귀호출에 비해 동적 프로그래밍(Dynamic Programming)이 얼마나 빠른지 체감할 수 있는 문제였다.
  2. 앞으로 문제를 풀 때에 동적 프로그래밍 기법을 잘 활용해서 시간을 단축하자!
  3. 때로는 수열의 요소를 여러 번 불러와야한다면, 그냥 fibonacci 수열을 쫙 구해놓고 리스트에 저장하는 것도 한 방법이다.