BOJ 2748

Input

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

import sys
input = sys.stdin.readline

n = int(input())

Output

첫째 줄에 n번째 피보나치 수를 출력한다.

print(arr[-1])

DP

재귀로 풀면 안 된다. 시간 초과 남

DP로 배열 써서 풀어야 한다.

arr = [0, 1]

for i in range(2, n+1):
  arr.append(arr[i-2] + arr[i-1])