[Baekjoon] 15990번: 1, 2, 3 더하기 5 / dynamic

https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

n을 1, 2 ,3 합으로 나타내는데, 합을 나타낼 때는 수를 1개 이상 사용해야 하고 , 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
예를 들어, 4를 1, 2, 3 합으로 나타내면 1+2+1 / 3+1 / 1+3 으로 3가지이다. 5는 1+3+1 / 2+1+2 / 2+3 / 3+2 로 4가지이다. 1, 2, 3의 합이므로 (n-1)번째의 마지막 숫자 개수 + (n-2)번째 마지막 숫자 개수 + (n-3)번째 마지막 숫자 개수에 각각 1, 2, 3을 더하면 원하는 결과를 얻을 수 있다.
그리고 같은 수를 두 번 이상 연속해서 사용하면 안되므로, dp[n][i] (i=1,2,3)조건으로 놓고 dp[n][1]이면 dp[n][1]을 제외한 dp[n][2] + dp[n][3]을 구하고, dp[n][2] 이면 dp[n][2]를 제외한 dp[n][1] + d[n][3]를 구하고 dp[n][3] 이면 dp[n][3]을 제외한 d[n][1] + dp[n][2] 를 구해서, n번째 숫자의 합 개수를 찾으려면 dp[n][1]+dp[n][2]+dp[n][3]을 모두 더하면 된다. main함수에 선언하면 stack영역에 할당되서 배열에 SIZE(10001) 크기는 불가능하기때문에 전역변수로 선언하여 data영역에 할당해준다.

코드

//15990
#include <iostream>
#include <cstring>
using namespace std;
#define SIZE 100001
long long dp[SIZE][4];

int main(int argc, const char * argv[]) {
  
    int T, n;
    for(int i=0;i<SIZE;i++) memset(dp[i], 0, sizeof(int)*4);
    cin>> T;
    
    dp[1][1] = dp[2][2] = dp[3][3] = 1;
    dp[3][1] = dp[3][2] = 1;
    for(int i=4;i<=SIZE;i++){
           dp[i][1] = (dp[i-1][2] + dp[i-1][3])%1000000009;
           dp[i][2] = (dp[i-2][1] + dp[i-2][3])%1000000009;
           dp[i][3] = (dp[i-3][1]+ dp[i-3][2])%1000000009;
    }
    
    for(int i=0;i<T;i++){
        cin>> n;
        cout<<(dp[n][1] + dp[n][2] + dp[n][3])%1000000009 << "\n";
    }
    
    return 0;
}