백준 9095번 C/C++

이전의 문제인 2xn과 비슷한 형식의 dp문제라서 그런지 시간이 별로 걸리지 않았다.
시간 초과가 나올거 같아서 동일하게 배열을 활용하여 풀기로 하였고
이 문제 또한 규칙성을 빠르게 알아차렸다.

예를 들어 8의 예시를 들자면
7, 6, 5의 경우의 수를 더하면 8이 나왔다.
4까지는 숫자가 문제에 나와있어서 5까지만 구해봐도 그 규칙성이 눈에 띄게 보였다.
코드는 이렇게 만들었다.

#include <stdio.h>

int main()
{
int a[1001];
a[1] = 1;
a[2] = 2;
a[3] = 4;

int result[1001];

int testcase;
scanf("%d", &testcase);

for (int j = 0; j < testcase; j++) {
    int n;
    scanf("%d", &n);        

    for (int i = 4; i <= n; i++) {
        a[i] = a[i - 1] + a[i - 2] + a[i - 3];
    }
    result[j] = a[n];        
}

for (int j = 0; j < testcase; j++) {
    printf("%d\n", result[j]);
}

}

testcase 변수에 몇개를 할것인지에 대해 정보를 입력 받아 for문을 반복시켰고
궁금한 수를 입력을 받은 후 모두 출력을 해야하는 형식이므로
result배열에 결과값을 저장한 후
마지막 for문을 활용해 출력을 했다.

2xn문제를 통해 dp는 배열을 활용하는 것이 좋다고 알고 있었다면
이 문제를 풀이하는데에는 큰 어려움이 없을것 같다.