2133 타일 채우기

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

2133번: 타일 채우기

 

d[i][j] = 3*i를 채우는 방법의 수, i열의 상태는 j

 

상태 다이나믹을 이용해서 경우의 수들을 구할 수 있다. 그림을 그려보면 쉽게 이해할 수 있다. i열을 계산할 때 i-1열은 꽉 차 있어야 한다.

 

#include <cstdio>
 
int n,d[31][8];
 
int main()
{
    scanf("%d",&n);
    d[0][7]=1;
    for(int i=1;i<=n;i++)
    {
        d[i][0]=d[i-1][7];
        d[i][1]=d[i-1][6];
        d[i][2]=d[i-1][5];
        d[i][3]=d[i-1][4]+d[i-1][7];
        d[i][4]=d[i-1][3];
        d[i][5]=d[i-1][2];
        d[i][6]=d[i-1][1]+d[i-1][7];
        d[i][7]=d[i-1][0]+d[i-1][3]+d[i-1][6];
    }
    printf("%d",d[n][7]);
    return 0;
}