[백준] 15990 1,2,3 더하기 5

 

123더하기에서 조건이 추가되었다

바로 연속된 숫자는 사용할 수 없다는 것이다

 

그럼 어떻게 문제를 해결해야할까

 

우리는 테이블에 하나의 정보를 더 저장하면 된다!

바로 마지막 숫자다

 

숫자 n을 만들 때 마지막이 1이라면

n-1을 만드는 경우의 수에서 마지막이 2,3인 경우만 더하면 된다

 

이런식으로 나머지도 채워나가면 된다!

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const ll mod = 1e9+9;
int n;
ll d[100005][5];
 
int main(){
    
    d[1][1]=1;
    
    d[2][2]=1;
    
    d[3][1]=1;
    d[3][2]=1;
    d[3][3]=1;
 
    for(int i=4;i<=100000;i++){
        d[i][1] +=d[i-1][2];
        d[i][1]%=mod;
 
        d[i][1] +=d[i-1][3];
        d[i][1]%=mod;
 
        d[i][2] +=d[i-2][1];
        d[i][2]%=mod;
 
        d[i][2] +=d[i-2][3];
        d[i][2]%=mod;
 
        d[i][3] +=d[i-3][1];
        d[i][3]%=mod;
 
        d[i][3] +=d[i-3][2];
        d[i][3]%=mod;
    }
    
    scanf(" %d",&n);
    while(n--){
        int t; scanf(" %d",&t);
        ll ans = d[t][1]+d[t][2]+d[t][3];
        ans%=mod;
        printf("%lld\n",ans);
    }
}