[백준] 1003번 피보나치 함수 (Python 파이썬)

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

문제 설명

자세한 문제 설명은 위의 링크에 나와있습니다!

 

피보나치 함수란, N번째 수의 값이 N-1 + N-2 의 값이 되는 함수입니다.

fibonacci(N) 을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 문제입니다.

---

풀이 과정

이 문제를 문제에서 주어진 C++코드를 그대로 이용해 0과 1의 횟수를 구하려고 하면 시간초과가 난다.

왜냐하면 f(10)을 호출했다고 가정할 때, f(10) = f(9) + f(8)이 되기 때문에 

f(9)와 f(8)을 한번씩 호출하게 되는데,

f(9) = f(8)+f(7) 이므로 f(9)가 f(8)을 한번 더 호출 하게 된다.

이런 식으로, 중복되어 호출되는 경우가 많이 생기기 때문에 이 방식을 이용하면 안된다.

 

한번 구한 수는, 다시 구하지 않고 값을 저장하여 이용할 수 있도록

DP(Dynamic Programming)개념을 이용하면 된다.

 

d라는 리스트를 2차원으로 만들어 d[x][0]에는 0이 호출된 횟수, d[x][1]에는 1이 호출된 횟수를 저장하였다.

0일 경우는 1, 0

1일 경우는 0,1 이 고정이므로 이 두개 값만 고정값으로 두고

3부터는 이전의 값을 이용해 구하도록 구현하였다.

 

t = int(input())

for i in range(t):
    n = int(input())

    if n == 0:
        print("1 0")
    elif n == 1:
        print("0 1")

    else:
        d = [[0] * 2 for _ in range(n + 1)]
        d[0][0] = 1
        d[1][1] = 1
        d[2] = [1, 1]
        for j in range(3, n + 1):
            d[j][0] = d[j - 1][0] + d[j - 2][0]
            d[j][1] = d[j - 1][1] + d[j - 2][1]

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

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !