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

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

문제

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

---

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

입/출력

---

풀이

n = int(input())
dp = [(1,0),(0,1),(1,1),(1,2)] + [(0,0) for _ in range(37)]

for _ in range(n):
  N = int(input())
  for i in range(4,N+1):
    dp[i] = (dp[i-1][0] + dp[i-2][1] ,dp[i-1][1]+dp[i-2][1])
  print(*dp[N])

결과

---

느낀 점

피보나치 의 수를 변형해서 나온 문제이다. 문제를 점화식으로 풀자면 F(n) = F(n-2)+F(n-1) 형태이다. 표로 구현해서 풀자면

0 = (1,0) , 1 = (0,1) , 2 = (1,1) , 3 = (2,1) , 4 = (2,3)...으로 나타내 진다. 점화식은 알겠지만 점화식을 토대로 구현하는 것이 어려웠다. 값이 2개이므로 2중 반복문으로 푸는 것까지는 괜찮았으나 dp테이블 안에 값을 얻어내는 방식에서 계속 어려웠던 것 같다. 

print(*)을 이용해서 안의 값들만 뽑아내서 해결할 수 있었다.