1003번 : 피보나치 함수

기본적인 DP입니다.

0에서 0의 개수는 1개, 1의 개수는 0개

1에서 0의 개수는 0개, 1의 개수는 1개

2는 0과 1로 쪼개지면서

        0의 개수는 1개, 1의 개수는 1개

3은 1과 2로 쪼개지면서

  0의 개수는 1개, 1의 개수는 2개

4는 2와 3으로 쪼개지면서

  0의 개수는 2개, 1의 개수는 3개

즉, 4에서의 0의 개수는 2에서의 0의 개수와 3에서의 0의 개수를 더하면 되겠죠. 1도 마찬가지구요

#include <stdio.h>

int dp[100][2]; //[0] : 0, [1] : 1

int T;

int f_0(int n) {

if (dp[n][0]!=-1) return dp[n][0];

else return dp[n][0]=f_0(n - 1) + f_0(n - 2);

}

int f_1(int n) {

if (dp[n][1]!=-1) return dp[n][1];

else return dp[n][1]=f_1(n - 1) + f_1(n - 2);

}

int main() {

for (int i = 0; i < 100; ++i) {

for (int j = 0; j < 2; ++j) {

dp[i][j] = -1;

}

}

scanf("%d", &T);

dp[0][0] = 1;

dp[0][1] = 0;

dp[1][0] = 0;

dp[1][1] = 1;

for (int i = 2; i < 100; ++i) {

f_0(i);

f_1(i);

}

while (T--) {

int N;

scanf("%d", &N);

printf("%d %d\n", dp[N][0], dp[N][1]);

}

}