[백준] 1003번 피보나치 함수 파이썬 정답 코드

1003번: 피보나치 함수

---

1. 문제 내용

 

 

2. 접근 방식

• 다이나믹 프로그래밍이다.

일반적인 재귀 함수로는 N이 조금만 커져도 시간 초과가 난다. 따라서 다이나믹 프로그래밍 방식으로 접근해야 한다.

 

• dp 리스트는 각 n의 0과 1의 개수가 담긴 2차원 리스트이다.

이 문제에서 실제 n = 4일 때의 피보나치 수를 구할 필요가 없다. 단지 n = 4일 때 0과 1이 몇 번 호출되는지만 궁금하기 때문이다. f(5)로 예를 들어보자.

f(5)는 위와 같은 f() 함수들이 호출된다. f(2)는 0과 1을 각각 1개씩 가지고 있으므로, [1, 1]로 표현할 수 있다. f(3)은 f(2) 값에서 1의 값만 늘리면 되므로, [1, 2]가 된다. f(4)는 f(2)의 [1, 1]과 f(3)의 [1, 2]를 각각 더한 [2, 3]이다. 최종적으로 f(5)는 f(3)의 [1, 2]과 f(4)의 [2, 3]을 각각 더한 [3, 5]이다.

 

 

3. 정답 코드

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

    dp = [0] * (n + 2)
    dp[0] = [1, 0]
    dp[1] = [0, 1]

    for i in range(2, n + 1):
        if not dp[i]:
            c0 = dp[i-1][0] + dp[i-2][0]
            c1 = dp[i-1][1] + dp[i-2][1]
            dp[i] = [c0, c1]

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