[CodeUp] 1915번, 1916번 : (재귀함수) 피보나치 수열 (Large) (Python)

[CodeUp] 1915번, 1916번 : (재귀함수) 피보나치 수열 (Large) (Python)

 

 

Python

 

1915 방법 1 - 메모리 27724 / 시간 18 / 코드 길이 106B

def f(n):
  if n == 1 or n == 2:
    return 1
  return f(n-2)+f(n-1)  

t = int(input())
print(f(t))

 

1915 방법 2

(만약 while을 쓸 수 있다면)

def f(n):
  idx, a, b = 0, 0, 1
  while idx < n:
    idx, a, b = idx + 1, b, a + b
  return a

N = int(input())
print(f(N))

 

 

1916 방법 1 - 메모리 27724 / 시간 18 / 코드 길이 161B

 

주의 : 시간초과 -> DP의 전형적인 문제로 판단하여 Memorization이 필요!!!

def f(n):
  if n == 1 or n == 2:
    return 1
  return f(n-2)+f(n-1)

N = int(input())
print(f(N) % 10009)

Memorization을 위해 l이라는 list를 사용하여 저장합니다. 또한 필요시 저장한 list 위치를 뽑아옵니다.

def f(n):
  if n == 0 or n == 1:
    return n
  if l[n] == 0:
    l[n] = f(n-1) + f(n-2)
  return l[n]
  
N = int(input())
l = [0]*201
print(f(N)%10009)