[알고리즘/문제풀이][BOJ 1003번] 피보나치 함수

피보나치 함수 문제는 동적 프로그래밍 기법을 사용하여 해결할 수 있는 문제입니다. 피보나치 함수를 재귀함수를 이용하여 계산하게 되면 많은 시간이 걸리게 됩니다. 따라서 배열을 사용하는 동적 프로그래밍 기법을 이용하여 구현하여야만 시간을 절약할 수 있습니다.

작성한 코드는 다음과 같습니다.

#include<stdio.h>
#pragma warning(disable : 4996)
//https://ark-hive.tistory.com

int T;
int N;
long long fibo[50];

int main(void) {
	scanf("%d", &T);

	for (int i = 0; i < T; i++) {
		scanf("%d", &N);
		for (int j = 0; j <= 40; j++) {
			fibo[j] = 0;
		}


		fibo[N] = 1;
		for (int j = N; j > 1; j--) {
			for (int k = 0; k < fibo[j]; k++) {
				fibo[j - 1] += 1;
				fibo[j - 2] += 1;
			}
		}

		printf("%lld %lld\n", fibo[0], fibo[1]);
	}
}

문제는 다음의 링크에서 확인할 수 있습니다.

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