백준 15990 / 1,2,3 더하기 5

다이나믹 프로그래밍 연습문제

다이나믹 프로그램은 점화식 짜는 게 우선적으로 중요하기 때문에

좀 더 머리를 써야할 거 같다.

n을 완성하는 수식 중 i로 끝나는 식을 ans[n][i]라 하면

1,2,3 더하기의 점화식은

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

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

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

소스코드는

#include <stdio.h>
#include <iostream>
#include <vector>
 
using namespace std;
 
long long ans[100001][4];
 
int main() {
    int tastcase;
 
    cin >> tastcase;
 
    ans[0][1] = 0;
    ans[0][2] = 0;
    ans[0][3] = 0;
 
    ans[1][1] = 1;
    ans[1][2] = 0;
    ans[1][3] = 0;
 
    ans[2][1] = 0;
    ans[2][2] = 1;
    ans[2][3] = 0;
 
    ans[3][1] = 1;
    ans[3][2] = 1;
    ans[3][3] = 1;
 
    for (int i = 4; i <= 100000; i++) {
 
        ans[i][1] = (ans[i - 1][2] + ans[i - 1][3]) % 1000000009;
        ans[i][2] = (ans[i - 2][1] + ans[i - 2][3]) % 1000000009;
        ans[i][3] = (ans[i - 3][1] + ans[i - 3][2]) % 1000000009;
 
    }
 
    while (tastcase--) {
 
        int n;
 
        cin >> n;
        
        cout<< (ans[n][1] + ans[n][2] + ans[n][3]) % 1000000009 <<endl;
 
        
    }
 
}