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

🤔 문제

 

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

 

---

 

🔍 문제 풀이 과정

 

전형적인 dp 문제입니다. dp[n]에 fibonacci(n)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 저장하도록 해보겠습니다.

배열의 첫 원소는 0이 출력되는 횟수, 두 번째 원소는 1이 출력되는 횟수를 저장하는 식으로 구현하겠습니다.

 

먼저 손으로 dp[0]부터 값을 채워보면서 규칙을 찾아보겠습니다.

 

dp[0]과 dp[1]은 예시에서도 나와있듯이 [1,0]과 [0,1]입니다.

dp[2]는 dp[0]과 dp[1]을 호출하므로 두 값을 합한 값인 [1,1]이 되고,

마찬가지로 dp[3]도 dp[1]과 dp[2]를 합한 값이 됩니다.

 

dp[i][0] = dp[i - 1][0] + dp[i - 2][0]
dp[i][1] = dp[i - 1][1] + dp[i - 2][1]

 

따라서, 위와 같은 점화식을 구할 수 있습니다. 이를 이용해서 문제를 다음과 같이 해결 가능합니다.

 

import sys
input = sys.stdin.readline

dp = [[0, 0] for _ in range(41)]
dp[0] = [1, 0]
dp[1] = [0, 1]

for i in range(2, 41):
    dp[i][0] = dp[i - 1][0] + dp[i - 2][0]
    dp[i][1] = dp[i - 1][1] + dp[i - 2][1]

t = int(input())

for _ in range(t):
    n = int(input())
    print(dp[n][0], dp[n][1])

 

 

n<=40 이므로 dp[40]까지 미리 계산한 뒤, 입력에 따른 결과만 출력해주면 됩니다.

 

---

 

📜 결과