[백준 15988번] [동적 계획법] 1, 2, 3 더하기 3

dp[n] : 정수 n을 1, 2, 3의 합으로 나타내는 방법

 

점화식

dp[n] = dp[n - 1] + dp[n - 2] + dp[n -3]

단, dp[1] = 1, dp[2] = 2, dp[3] = 4는 Base input 값이므로 따로 설정해준다.

 

잘 생각해보면

시작은 1, 2, 3일수 밖에 없고

그 뒤는 dp의 다른 값으로 표현함으로써 점화식을 세울 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
typedef long long ll;

using namespace std;
ll dp[1000001];

ll sum(int n){
    if(n == 1 || n == 2 || n == 3) return dp[n];
    if(dp[n - 1] == 0) sum(n - 1);
    return dp[n] = (dp[n - 1] + dp[n - 2] + dp[n - 3]) % 1000000009;
}

int main(void){
    memset(dp, 0, sizeof(dp));

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

    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        int temp;
        cin >> temp;
        cout << sum(temp) << "\n";
    }

    return 0;
}