[백준/C++] 15988번: 1, 2, 3 더하기 3

 

풀이

#include <iostream>
#define MAX 1000001
#define MOD 1000000009

int n;
long long d[MAX];
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    d[1] = 1, d[2] = 2, d[3] = 4;

    while(T--) {
        cin >> n;

        for( int j = 4; j <= n; ++j ) {
            d[j] = (d[j - 3] + d[j - 2] + d[j - 1]) % MOD;
        }

        cout << d[n] % MOD << '\n';
    }

    return 0;
}

d[n]을 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수라고 하면, d[1] = 1 (1), d[2] = 2 (1, 1),(2), d[3] = 4(1, 1, 1), (1, 2), (2, 1), (3)이고 i가 3보다 크다고 했을 때, d[i]는 d[1], d[2], d[3]을 통해서 표현할 수 있다. ex) d[4] = (1, 3), (2, 2), (3, 1) 등

이를 활용해서 d[j]에 대한 식을 구하고 이를 MOD의 값으로 나눈 나머지를 출력