[DP] 15989번 - 1,2,3 더하기 4 (26일차)

//scanf 경고를 막기 위한 선언
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
//malloc과 calloc을 사용하기 위한 선언
#include <stdlib.h>
//입력받은 수에 대해 1,2,3으로 구성가능한 조합의 수를 찾는 함수 선언
int finder(int n);
//입력받은 수에 대해 1,2,3으로 구성가능한 조합의 수를 찾는 함수 선언
int finder(int n)
{
    //1,2,3 각 숫자를 최고로 큰 숫자로 하는 숫자들의 조합을 저장하는 DP 2차원 배열 동적 할당
    //DP 배열 중 1차원 요소를 생성
    int **dp = (int **)calloc(n, sizeof(int));
    //DP 배열 중 2차원 요소의 수 만큼 반복
    for(int i=0; i<n; i++)
    {
        //DP 배열 중 1차원 각 요소 인덱스에 대해 크기 3*(int)만큼의 배열 생성
        dp[i] = (int *)calloc(3, sizeof(int));
    }
    //1차원 배열의 개수만큼 반복
    for(int j=0; j<n; j++)
    {
        //숫자가 1일 경우
        if(j == 0){
            //1 혼자로만 이루어지기 때문에 [1,0,0]
            dp[0][0] = 1;
        }
        //숫자가 2일 경우
        else if(j == 1){
            //11과 2 두 개로 이루어지기 때문에 [1,1,0]
            dp[1][0] = dp[1][1] = 1;
        }
        //숫자가 3일 경우
        else if(j == 2){
            //111과 21과 3 세 개로 이루어지기 때문에 [1,1,1]
            dp[2][0] = dp[2][1] = dp[2][2] = 1;
        }
        //그 이상일 경우
        else{
            //해당 숫자의 1로만 이루어진 부분은 해당 숫자-1인 숫자의 1로만 이루어진 부분과 같음
            dp[j][0] = dp[j-1][0];
            //해당 숫자의 2~1로만 이루어진 부분은 해당 숫자-2의 2~1로만 이루어진 부분과 같음
            dp[j][1] = dp[j-2][1] + dp[j-2][0];
            //해당 숫자의 3~1로만 이루어진 부분은 해당 숫자-3의 3~1로만 이루어진 부분과 같음
            dp[j][2] = dp[j-3][2] + dp[j-3][1] + dp[j-3][0];
        }

    }
    //가장 마지막 숫자의 1,2,3 각 부분에 대한 조합의 수의 합을 반환
    return (dp[n-1][0] + dp[n-1][1] + dp[n-1][2]);
}
//메인 함수
int main()
{
    //입력받을 횟수 선언
    int num;
    //입력받을 횟수 입력
    scanf("%d", &num);
    //입력받아야 할 횟수만큼 반복
    for(int i=0; i<num; i++)
    {
        //입력받을 수 선언
        int a;
        //입력받을 수 입력
        scanf("%d", &a);
        //입력받은 수에 대해 1,2,3으로 이루어진 모든 조합의 수의 합을 출력
        printf("%d\n", finder(a));
    }
}