[2133번] 타일 채우기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

상태 다이나믹을 이용하여 풀 수 있는 문제이다.

상태 다이나믹이란? 현재 내가 이 상태가 되기 위해 이 전 DP가 어떻게 형성되있어야 할 지 고려하는 DP 방식이다.

아래 그림을 보면 현재 0~7번 상태가 존재하게 된다.

왜냐면 3xN의 타일이기에 마지막 타일 모습이 0번처럼 아무것도 없는 상태일 수도 있고

마지막 7번처럼 모두 꽉찬 상태의 타일일 수도 있기 때문이다.

우선 0의 상태가 될 때를 보자.

0의 상태가 되기 위해서는 바로전 상태가 꽉 차있는 상태여야 한다.

그래야만 2x1, 1x2 타일로 채우지 않고 0의 상태를 유지 할 수 있기 때문이다.

DP[i][0] = DP[i - 1][7];

1의 상태가 될 때를 보자.

1의 상태가 되기 위해서는 이전 상태가 6이어야 하고 6에서 주황색 타일인 1x2타일이 들어온다면 다음은 1의 상태로 변할 것이다.

DP[i][1] = DP[i - 1][6];

2의 상태가 될 때를 보자.

2의 상태가 될 때는 5의 상태에서 1x2의 타일이 중간에 넣어진다면 그 다음 상태가 2의 상태로 변할 것이다.

DP[i][2] = DP[i - 1][5];

3의 상태가 될 때를 보자.

4의 상태에서 주황색 타일인 1x2 타일과 노랑색 타일인 1x2 타일 두개가 들어온다면 3의 상태가 될 수 있고,

7의 상태에서 2x1인 타일이 들어온다면 3의 상태가 될 수 있다.

DP[i][3] = DP[i - 1][4] + DP[i - 1][7];

4의 상태가 될 때를 보자.

4의 상태는 3의 상태에서 1x2 타일이 들어와야 4의 상태가 된다.

DP[i][4] = DP[i - 1][3];

5의 상태가 될 때를 보자.

마찬가지로 2의 상태에서 주황, 노랑색 타일의 1x2 타일이 들어온다면 그 다음은 5의 상태가 될 수 있다.

DP[i][5] = DP[i - 1][2];

6의 상태가 될 때를 보자.

6의 상태는 1의 상태에서 1x2 타일이 두개 오거나 7의 상태에서 2x1 타일이 하나 오면 된다. 

DP[i][6] = DP[i - 1][1] + DP[i - 1][7];

마지막 7의 상태가 될 때를 보자.

7의 상태는 

0의 상태에서 1x2 타일이 3개 오거나,

3의 상태에서 1x2, 2x1 타일이 각각 한개씩 오거나, 

6의 상태에서 1x2, 2x1타일이 하나씩 오면 된다.

DP[i][7] = DP[i - 1][0] + DP[i - 1][3] + DP[i - 1][6];

소스 코드 : 

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int DP[31][8];
 
int main()
{
    int n;
 
    scanf("%d", &n);
 
    DP[0][7] = 1;
 
    for (int i = 1; i <= n; i++)
    {
        DP[i][0] = DP[i - 1][7];
        DP[i][1] = DP[i - 1][6];
        DP[i][2] = DP[i - 1][5];
        DP[i][3] = DP[i - 1][4] + DP[i - 1][7];
        DP[i][4] = DP[i - 1][3];
        DP[i][5] = DP[i - 1][2];
        DP[i][6] = DP[i - 1][1] + DP[i - 1][7];
        DP[i][7] = DP[i - 1][0] + DP[i - 1][3] + DP[i - 1][6];
    }
 
    printf("%d", DP[n][7]);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>