[2133번] 타일 채우기

2133번: 타일 채우기

 

www.acmicpc.net

가로가 N, 세로가 3인 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구하는 문제다.

간단한 DP 예제 중 하나다.

가로가 1일 때, 채울 수 있는 경우의 수는 0이다. 그렇기 때문에 N이 홀수 일 경우 벽을 채울 수 없다.

가로가 2일 때, 채울 수 있는 경우의 수는 3이다.

가로가 4일 때, 가로가 2인 경우를 2번 계산하면 되겠다고 생각하겠지만 예외적인 모양이 존재한다.

맨 아래 2개의 경우가 가로가 2일 때와는 다른 모양으로 채울수 있는 경우인데 이런 경우가 N이 증가할 수록 늘어난다. 

규칙을 찾아보면 아래와 같이나온다.

이 규칙으로 점화식을 만들어 보면

경우의 수 = A[N-2] * 3 + (* 2)가 된다.

(에서 x가 홀수 일 때는 배열에 0이 들어 있기 때문에 더하기 값에 영향을 주지 않는다.)

/*2133번 타일 채우기*/
#include <iostream>
using namespace std;
int N;
int tile[30] = { 1,0,3, };
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N;
    if (N % 2 == 0) {
        for (int i = 4; i <= N; i += 2) {
            tile[i] = tile[i - 2] * 3;//만들어 둔 타일로 구하는 경우
            for (int j = 4; i - j >= 0; j+=2) tile[i] += tile[i - j] * 2; //예외적인 경우
        }
    }
    cout << tile[N];
}