[백준/C++] 2133번: 타일 채우기

문제 & 링크

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

풀이

1. bottom-up 방식으로 dp 테이블을 채운다.

2. 타일의 크기가 2이기 때문에 N이 홀수일 경우 벽을 채울 수 없다. 따라서 N이 짝수일 경우만 생각한다.

3. 기본적으로 N이 2씩 증가될 때 마다 기존의 개수에 3을 곱해준다. (3 x 2의 타일을 채우는 방법이 3가지)

4. N이 2씩 증가되며 새로운 모양이 등장한다.

1. 위의 모양을 고려하여 점화식을 구한다. (아래의 사진 참고)

코드

#include <iostream>

using namespace std;

int dp[31];

int main() {
    int N;

    cin >> N;

    dp[0] = 1; // dp 테이블을 채우기 위함
    dp[2] = 3;

    int sum = 0;
    for (int i = 4; i <= N; i += 2) {
        sum += dp[i - 4]; 
        dp[i] = dp[i - 2] * 3 + sum * 2;
    }

    cout << dp[N];
}