[백준] 2133 타일 채우기, C++

2133번: 타일 채우기

문제 요약

3xN 크기의 벽을 2x1, 1x2의 타일로 채우는 경우의 수

접근

1. 규칙찾기

n이 홀수면 만들수 없음
n이 짝수인 경우 만들수 있음.
n= 2: 3개
n= 4:
(n = 2인 타일에 n = 2인 타일을 추가하는 경우) + (n=4인 타일을 추가하는 경우, 새로운 타일)
3*3 + 2 개 = 11개

n= 6:
(n = 4인 타일에 n = 2인 타일을 추가하는 경우)
+ (n = 2 인 타일에 n=4인 타일을 추가하는 경우)
+ (n = 6 인 타일을 추가하는 경우, 새로운 타일)
- (중복값 제거)
11*3 + 2 + 2*3 = 33 + 2 + 6 = 41개

점화식
memo[N] = memo[N-2] * memo[2] + 2 + sum(memo[N-i] * 2) (i = 4 ~ N - 2)

1. 크기가 N-2인 타일에 길이가 2인 타일을 붙인 경우; memo[N-2] * memo[2]
2. 크기가 N인 경우(특이 케이스); 2
3. (크기가 N-i 인 개수) * (타일 길이가 i인 경우의 특이 케이스, 2);

알고리즘

1. 점화식을 구하면된다.

새로 알게된 것

X

전체 코드

#include <iostream>

#define SIZE 31
using namespace std;

int memo[SIZE] = {0, 0, 3,};

int main()
{
    for (int i = 4; i < SIZE; i += 2)
    {
        memo[i] = memo[i - 2] * 3 + 2;
        for (int j = i - 2; j > 2; j -= 2)
        {
            memo[i] += 2 * memo[i-j];
        }
    }

    int N;
    cin >> N;
    cout << memo[N] << endl;
    return 0;
}