백준 BOJ 12849 본대산책

예전에 어떤 알파벳은 특정 알파벳 다음에만 올 수 있다는 규칙의 문제와 같다

 (ex u는 e,i,o 다음에 올 수있고 e 는 a,u,o 다음에 올 수있고..)

 

특정시점의 어느 위치는 그 바로 이전의 연결된 위치에서만 올 수 있다

 

#include<iostream>
#include<memory.h>
#include<vector>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<string>
#include<cmath>
#define INF 1e9
#define MOD 1000000007
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
int n, m, k;
 
int dp[8][100001];
int pre[8][4] = {
    {1,2,-1,-1},
    {0,2,3,-1},
    {0,1,3,4},
    {1,2,4,5},
    {2,3,5,6},
    {3,4,7,-1},
    {4,7,-1,-1},
    {5,6,-1,-1}};
 
int main() {
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL);
    
    scanf("%d",&n);
    
    memset(dp,0,sizeof(dp));
    
    dp[1][1]=1;
    dp[2][1]=1;
    for(int i=2;i<=100001;i++){
        for(int j=0;j<8;j++){
            for(int k=0;k<4;k++){
                if(pre[j][k] == -1) continue;
                dp[j][i] = (dp[pre[j][k]][i-1] + dp[j][i]) %MOD;
            }
        }
    }
    
    printf("%d\n",dp[0][n]);
    
    
    return 0;
}