[백준 1003] 피보나치 함수

문제

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

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

1 2 3 4 5 6 7 8 9 10 11

int fibonacci(int n) {     if (n == 0) {         printf("0");         return 0;     } else if (n == 1) {         printf("1");         return 1;     } else {         return fibonacci(n‐1) + fibonacci(n‐2);     } }

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이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

3
0
1
3

출력

1 0
0 1
1 2

fibonacci(n) 이하 fi(n)은 피보나치 함수이다.

fi(0)과 fi(1)은 각각 0과 1을 반환하며 fi(2)는 fi(1)+fi(0)임을 알 수 있다.

이때 fi(1)은 1이 출력되는 횟수 fi(0)은 0이 출력되는 횟수로 접근하면 된다.

fi(2) = fi(1) + fi(0)

fi(3) = fi(2) + fi(1) = fi(1) + fi(0) + fi(1)

fi(4) = fi(3) + fi(2) =  fi(1) + fi(0) + fi(1) + fi(1) + fi(0) 

==> fi(1) + fi(0) + fi(1) + fi(1) + fi(0) 

fi(5) = fi(4) + fi(3) = fi(1) + fi(0) + fi(1) + fi(1) + fi(0) + fi(1) + fi(0) + fi(1)

==> fi(1) + fi(0) + fi(1) + fi(1) + fi(0) + fi(1) + fi(0) + fi(1)

	0 횟수	1 횟수
fi(2)	1	1
fi(3)	1	2
fi(4)	2	3
fi(5)	3	5

표를 보면 더 쉽게 규칙을 찾을 수 있다

즉 fi(4) 에서 0과 1의 횟수는 fi(2)의 횟수 + fi(3)의 횟수 이며 

fi(5)도 fi(4)의 횟수 + fi(3)의 횟수이다.

따라서 fi(n) = fi(n-1) + fi(n-2) 라는 점화식을 뽑아낼 수 있다.

소스

// //  main.cpp //  DP // //  Created by seungwoo on 2018. 06. 28 //  Copyright © 2018년 seungwoo. All rights reserved. // #include <iostream> #include <algorithm> using namespace std; void fibo(int n); void init(); int dp[2][41] = {0}; int main() { int T,n; // 0<=n<=40 cin>>T; init(); while(T>0){ T--; cin>>n; fibo(n); cout<<dp[0][n]<<" "<<dp[1][n]<<endl; } return 0; } void fibo(int n) { for(int i=2;i<=n;i++){ dp[0][i] = dp[0][i-1] + dp[0][i-2]; dp[1][i] = dp[1][i-1] + dp[1][i-2]; } } void init() { dp[0][0] = 1; dp[0][1] = 0; dp[1][0] = 0; dp[1][1] = 1; }

이와 같이 2차원 배열을 이용하여 쉽게 프로그램을 구현할 수 있다.

dp로 풀이하지 않아도 쉬운 문제이나 dp로 풀지 않은 소스와 dp로 푼 소스는 실행시간에 큰 차이를 보인다.