[백준] 2747번 피보나치 수 문제풀이(python)

 

문제링크:

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

2747번: 피보나치 수

 

 

python 풀이

memo = [0] * 50
def 피(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif memo[n]:
        return memo[n]

    memo[n] = 피(n - 1) + 피(n - 2)
    return memo[n]
    
    
a = int(input())
print(피(a))

 

 

 

 

---

2747번 문제는 일반적인 재귀함수로 풀이를 하면 시간초과가 난다.

그래서 메모이제이션 기법을 사용해야 한다.

(메모이제이션 기법: 재귀 반복하지 않으려고 기록해놓는거)

 

메모이제이션 기법을 사용하지 않으려면 차라리

for 문쓰는게 나을수도 있다.

 

 

 

for 문 사용한 풀이

def 피(n):
    memo = [0, 1]
    for i in range(2,n+1):
        memo.append(memo[i-1] + memo[i-2])
    return memo[n]

a = int(input())
print(피(a))

 

 

오류난 문제풀이

def 피(n):
    if n == 0:
        return 0
    elif n == 1:
        return 110
    return 피(n - 1) + 피(n - 2)
    
a = int(input())
print(피(a))