[DP] [BOJ 1003] 피보나치 함수

 

1003번: 피보나치 함수

문제

피보나치 함수의 변형 문제로, f(n)을 호출할 때, f(0)과 f(1)의 횟수를 각각 출력하는 문제 (f = 피보나치 함수)

 

해석

오늘은 태블릿을 놓고와서 그림은 없다.

 

이 문제는 처음에 알쏭달쏭하다. 내가 풀어봤던 피보나치 함수는 함숫값만 구하면 됐는데, 호출 횟수를 구하라니? 그리고 사실은 문제가 2개다. 0을 호출하는 횟수와 1을 호출하는 횟수. 그래서 두 문제를 한꺼번에 풀다 보니 헷갈리는 부분이 있다.

 

하지만 결국 푸는 방식은 완전히 동일하다. 피보나치 함수에서 f[n] = f[n-1] + f[n-2]라는 식으로 풀었던 것처럼,

(f(n)에서 f(0)을 호출하는 횟수) = (f(n-1)에서 f(0)을 호출하는 횟수) + (f(n-2)에서 f(0)을 호출하는 횟수)

(f(n)에서 f(1)을 호출하는 횟수) = (f(n-1)에서 f(1)을 호출하는 횟수) + (f(n-2)에서 f(1)을 호출하는 횟수)

가 성립한다. 왜냐? 그림을 그려보면 눈에 보인다. 무튼 간에, 따라서 피보나치 함수 문제와 같은 점화식으로 문제를 풀 수 있다. 단, 0, 1에 대해서 모두 정답을 구해야 하므로 배열이 2개 필요하다.

 

다시 정리하면, 다음과 같이 풀 수 있다.

zero : f(0)의 호출 횟수를 저장하는 배열, one : f(1)의 호출 횟수를 저장하는 배열

초기값 정하기 : 

zero[0] : f(0)은 f(0)을 1번 호출하므로 zero[0] = 1

zero[1] : f(1)은 f(0)을 0번 호출하므로 zero[1] = 0

one[0] : f(0)은 f(1)을 0번 호출하므로 zero[0] = 0

one[1] : f(1)은 f(1)을 1번 호출하므로 zero[1] = 1

 

점화식으로 풀기 : 

zero[n] = zero[n-1] + zero[n-2]

one[n] = one[n-1] + one[n-2]

 

구현