[백준] 17175 피보나치는 지겨웡~ - python

백준 실버3 17175 피보나치는 지겨웡~ python

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

17175번: 피보나치는 지겨웡~

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 31256KB | 시간 40ms | 코드 길이 159B

import sys
N = int(sys.stdin.readline().rstrip())
d = [0] * 51
d[0] = 1
d[1] = 1
for i in range(2, N+1):
    d[i] = d[i-2] + d[i-1] + 1
print(d[N]%1000000007)

주어진 피보나치 함수를 이용한다면 시간초과가 납니다. 연산한 결과를 다시 쓰지 않고 해당 수만큼 더 연산하기 때문입니다. 그래서 다이나믹 프로그래밍(Dynamic Programming, 동적계획법) 을 이용하여 풀어야 합니다.

다이나믹 프로그래밍이란 연산한 결과를 필요할 경우 다시 쓰기 위해 '메모리에 저장'해두고 필요할 때 불러와서 다시 쓰는 방식입니다. 이러한 방식을 메모이제이션(memoization) 이라고 합니다.

---

Try 1.

시간초과가 뜬 코드입니다. - 코드 길이 233B

import sys
N = int(sys.stdin.readline().rstrip())
cnt = 1
def fibonacci(n):
    global cnt
    if (n < 2):
        return n
    else:
        cnt += 2
        return fibonacci(n-2) + fibonacci(n-1)
fibonacci(N)
print(cnt%1000000007)

---

Search 🔍

• 다이나믹 프로그래밍 (Dynamic Programming, 동적계획법)
  - 출처 : https://techblog-history-younghunjo1.tistory.com/183