1003 번 문제 피보나치 함수 Dynamic Programming

DP를 공부하는데 처음 해보면 괜찮을 문제같다. 

동전 문제를 바로 해보는 건 조금 어려운것 같기도 하고, 아무튼 

0을 호출했을때 0을 출력 1을 호출했을때 1을 출력.

이것을 계속 단계 별로 저장해 나아가면서, 최상단의 호출한 번호에서 

몇번을 출력해 주었는지 알아내면 된다. 

DP 배열

0

1

2

3

4

5

6

7

8

9

1/0

0/1

1/1

1/2

2/3

3/5

5/8

.

.

.

dp[0] = 1/0; dp[1] = 0/1;

2는 0과 1을 더한 것이고, 3은 2와 1의 결과 값을 더한 것이다. 

즉 앞에서 부터, 차례대로 결과값을 쌓아가면 된다. 

소스 보기

#include <stdio.h>

int main(){

    int dp[41][2]={0};

    int n=0,t=0;

    scanf("%d",&n);

    dp[0][0]=1; dp[0][1]=0;

    //0이 출력하는 0의 갯수 1, 1의 갯수 0

    dp[1][0]=0; dp[1][1]=1;

    //1이 출력하는 0의 갯수 0, 1의 갯수 1

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

        dp[i][0] = dp[i-1][0] + dp[i-2][0];

        dp[i][1] = dp[i-1][1] + dp[i-2][1];

        //2를 호출했을때 0과 1에서 나온 값을 더해서 저장

        //계산된 값을 중첩하여 더해 나감

    }

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

        scanf("%d",&t);

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

    }

    return 0;

}