[백준 1003] 피보나치 함수

문제 링크 : https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

사용 알고리즘 : 

동적 계획법

 

0이 출력되는 횟수와 1이 출력되는 횟수를 각각의 DP배열로 해결한다.

 

$F_n$을 n번째 피보나치 수에서 0이 출력되는 횟수라고 가정한다면

 

다음과 같은 점화식이 세워진다.

 

$$F_n = F_{n=1}+F_{n-2}$$

 

$F_0$은 1이고 $F_1$은 0이므로 모든 n에 대한 출력횟수를 n번의 연산으로 구할 수 있다.

 

1에 대한 점화식도 마찬가지로 세울 수 있다.

 

---

#include <stdio.h>

int main(void){
	int arr[45][2];
	arr[0][0] = 1;
	arr[0][1] = 0;
	arr[1][0] = 0;
	arr[1][1] = 1;
	for (int i = 2; i <= 40; i++){
		arr[i][0] = arr[i - 1][0] + arr[i - 2][0];
		arr[i][1] = arr[i - 1][1] + arr[i - 2][1];
	}
	int n;
	scanf("%d", &n);
	while (n--){
		int a;
		scanf("%d", &a);
		printf("%d %d\n", arr[a][0], arr[a][1]);
	}
}