1,2,3 더하기3 백준 15988

문제

1,2,3 더하기3 백준 15988번

리뷰

1,2,3더하기 문제와 똑같은데, 정수 n 의 크기제한과 출력의 조건을 주의해야 한다.

그래서 arr[i] 배열 자료형을 long long 으로 해줬고, 배열에 저장하기 전에 mod 연산을 해준다.

정수 i의 경우, 방법의 수를 D[i] 에 저장한다.

D[1] = 1

D[2] = 2

D[3] = 4

D[4] = 7

D[5] = 13

이렇게 되니까, 7 = 4 + 2 + 1 이었고, 13 = 7 + 4 + 2 였다.

[ 점화식 ]

D[i] = D[i-1] + D[i-2] + D[i-3]

코드

#include <stdio.h>
#define MODNUM 1000000009
using namespace std;

long long arr[1000000];

int sum_case(int num){

    int i = 0;

    for(i = 4; i <= num; i++){
        arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
        arr[i] %= MODNUM;
    }

    return arr[num];
}

int main(void){

    int test_case = 0, num = 0;

    scanf("%d", &test_case);

    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;

    while(test_case--){
        scanf("%d", &num);
        printf("%d\n", sum_case(num));
    }

    return 0;
}