[백준][DP] 타일채우기

1. 문제 주소

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

2133번: 타일 채우기

2. 문제

n이 홀수인 경우에는 타일을 채울 수 없다. 따라서 짝수인 경우만 고려해주면 된다.

먼저 가장 기본적인 단위의 도형은

다음과 같이 3가지 경우이다.

하지만 n이 4가 되는 경우

위 2개의 도형도 추가적으로 생기게 된다. 이를 고려하여 코드를 작성하면 된다.

3. 소스코드

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n;
    cin >> n;
 
    vector<int> dp(31);
 
    dp[0] = 1;
    dp[2] = 3;
    for (int i = 4; i <= n; i += 2) {
        for (int j = i - 4; j >= 0; j -= 2) {
            dp[i] += dp[j] * 2;
        }
        dp[i] += dp[i - 2] * 3;
    }
    cout << dp[n] << '\n';
    return 0;
}