[BOJ] 2133. 타일 채우기 ✔

2133. 타일 채우기

1. 문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

2. 입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

3. 출력

첫째 줄에 경우의 수를 출력한다.

4. 풀이

C++

#include <iostream>
using namespace std;

int N;
int dp[31] {1, 0, 3, };

int main()
{
    cin >> N;
    
    for (int i = 4; i <= N; i += 2)
    {
    	// i-2 번째 도형에서 3가지 경우의 도형 추가 가능
        dp[i] += 3 * dp[i - 2];
        // 위와 같은 특정 모형이 i-4, i-6, ... 번째 도형에 추가
        for (int j = i - 4; j >= 0; j -= 2)
            dp[i] += 2 * dp[j];
    }
    
    cout << dp[N];
}