[백준/Python] 1003번 피보나치 함수

---

문제

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

---

문제풀이

처음에는 재귀함수로 풀었는데 시간초과가 떠버렸다

# 시간초과 : 재귀함수

def fibo_zo(x):

    if x == 0:

        z, o = 1, 0

        return (z, o)

    elif x == 1:

        z, o = 0, 1

        return (z, o)

    else:

        return (fibo_zo(x-2)[0] + fibo_zo(x-1)[0], fibo_zo(x-2)[1] + fibo_zo(x-1)[1])

T = int(input())

for _ in range(T):

    n = int(input())

    print(fibo_zo(n)[0], fibo_zo(n)[1])

 

그래서 어떻게 풀지 고민하다가 다이나믹프로그래밍으로 풀면 시간초과를 해결할 수 있겠다는 생각을 했다

 

다이나믹 프로그래밍이란?

이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하는

즉, 중복되는 부분의 문제를 최소화하는 기법이다.

---

정답

# 다이나믹 프로그래밍

T = int(input())

d = [(1,0), (0,1)] + [(0,0) for _ in range(50)]

for _ in range(T):

    n = int(input())

    for i in range(2, n+1):

        d[i] = (d[i-1][0] + d[i-2][0], d[i-1][1] + d[i-2][1])

    print(d[n][0], d[n][1])

 

처음에는 d의 범위를 너무 적게 설정해 IndexError가 실행되었지만 추후에 범위를 늘려주고 해결하였다!

 

 

그런데 정답은 맞췄지만 갑자기 백준에 빨간체크가 떠서 크롬 확장프로그램에서 Cors를 설치하고 ON!으로 켜준 후 바로 해결되었다! 나름 우여곡절이 많았던 문제!