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

문제

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

 

입력

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

 

출력

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

---

DP를 이용하여 풀 수 있는 문제.

노가다

...이런식으로 노가다로 경우의 수들을 풀어쓰다보면 규칙을 발견하여 풀 수 있다. 사실 나는 구글링 해봐도 이해를 못해서 저렇게 풀었다.

 

3×N 크기의 벽을 1×2 타일 혹은 2×1 타일로 채울 수 있는 경우는 N이 짝수일 때 뿐이고, N이 2일때 기본적으로 채울 수 있는 타일의 모습은 다음과 같이 나온다.

D[2] = 3

그리고, N이 4 이상일 경우 위와 같이 각 타일의 길이만큼 배치할 수 있는 추가적인 경우들이 존재한다.

 

따라서 배치할 수 있는 경우의 수를 모두 정리하면 점화식은 다음과 같다.

 

1. n ≥ 2, D[n] = D[n - 2] * D[2] // D[2] = 3

2. n ≥ 4, D[n] = D[n - 4] * 2

 

3. n ≥ 6, D[n] = D[n - 6] * 2

...

...

➡️ D[n] = D[n - 2] * D[2] + D[n - 4] * 2 + ... + D[2] * 2 + D[0] * 2 (n ≥ 4)

 

위와 같이 규칙에 따라 나온 값들을 모두 더해주면 답이 나온다. 여기서 D[0]은 위의 N이 4 이상일 때의 그림처럼 자기 자신의 길이만큼 배치할 수 있는 경우로, D[0] = 1이다.

 

코드

#include <cstdio>
#include <vector>
#define MAX 31

using namespace std;
int DP(int num);
vector<int> memo(MAX, 0);

int main(void) {
    int n;
    scanf("%d", &n);
    printf("%d\n", DP(n));
    return 0;
}

int DP(int num) {
    memo[0] = 1;
    memo[2] = 3;

    for(int i = 4; i <= num; i++) {
        memo[i] += memo[i - 2] * memo[2];
        for(int j = 4; j <= i; j += 2) {
            memo[i] += memo[i - j] * 2;
        }
    }

    return memo[num];
}