[백준] 2748번: 피보나치 수 2 (파이썬)

문제

나의 첫번째, 두번째 제출(오답-시간초과)

def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1)+fib(n-2)
    
n=int(input())
dp=[fib(i) for i in range(n+1)]
print(dp[n])

동일한 코드를 python3와 pypy3로 제출했다..ㅎ
재귀로 풀면 시간초과가 발생하는 것을 알 수 있었다.

나의 최종 답안(정답)

n=int(input())
dp=[]
dp.append(0)
dp.append(1)

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

접근 방법

• dp문제, 재귀를 사용하지 않고 풀어주어야 한다.
• n이 0과 1일 땐 각각 0과 1의 값을 가지므로 미리 dp배열에 저장해두고, 반복문을 통해 2부터 n까지 순차적으로 구해준다.