백준(baekjoon) [C] - 1003번: 피보나치 함수

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

1003번: 피보나치 함수

---

#include <stdio.h>  // 피보나치 함수

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

	// 0과 1의 개수를 저장
	int dp[41][2];
	dp[0][0] = 1;
	dp[0][1] = 0;
	dp[1][0] = 0;
	dp[1][1] = 1;

	for (int i = 0; i < t; i++)
	{
		int n;
		scanf("%d", &n);
		for (int j = 2; j <= n; j++)
		{
			dp[j][0] = dp[j - 1][0] + dp[j - 2][0];
			dp[j][1] = dp[j - 1][1] + dp[j - 2][1];
		}
		printf("%d %d\n", dp[n][0], dp[n][1]);
	}

	return 0;
}

---

MEMO

-- 0과 1의 개수를 2차원 배열에 저장하여 사용하는 점이 핵심

 

!! dp는 조건이나 규칙 포기하지 않고 생각해보기 !!