[BOJ] 15988 : 1,2,3 더하기 3

풀이

시간복잡도 O(n)

dp[n]을 만들수 있는것은 dp[n-1]에서 1을 더하거나 dp[n-2]에서 2를 더하거나 dp[n-3]에서 3을 더하는 경우이다.

코드

#include <iostream>
using namespace std;

long long dp[1000001];
const int mo = 1000000009;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i <= 1000000; i++) {
        dp[i] = (dp[i - 1]%mo + dp[i - 2] % mo + dp[i - 3] % mo) % mo;
    }

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        cout << dp[n]<<'\n';
    }
    return 0;
}

Written on March 14, 2019