[BOJ] 2133 : 타일 채우기

문제 링크

2133번: 타일 채우기 (acmicpc.net)

2133번: 타일 채우기

대표적인 DP문제 2XN 타일링의 변형 문제.

풀이

2XN 타일과 다르게 여기서는 높이가 3이다.

N = 1 : 3X1크기의 벽을 2X1 타일을 가지고 채울 수 없다. DP[1] = 0

N = 2 : 3X2크기의 벽을 2X1 타일을 가지고 채우는 경우의 수는 3. DP[2] = 3 

이렇게 3가지가 있다

N = 3 : 3X3 벽을 2X1 타일을 가지고 채울 수 없다. DP[3] = 0

여기서 무언가를 눈치 챌 수 있다. N이 홀수인 경우에는 벽을 완전히 채우지 못한다.

그렇기 때문에 N이 홀수라면 경우의 수는 0이다.

N = 4 : N이 4일때는 기존에 구했던 N = 2인 경우를 조합해서 만들 수 있다.

DP[2] * DP[2] = 9. 그런데 N = 4 일 때만 만들 수 있는 벽의 모양이 있다. 

바로 이런 모양이다. 가로의 길이가 4일때만 만들 수 있는 모양이다. 위아래 뒤집을 수 있으므로

가로의 길이가 4일때만 만들 수 있는 경우의 수는 2가지.

DP[4] = 9 + 2 = 11 이다.

N = 6일때는 앞서 구한 N = 4 일 때의 경우에 뒤에 N = 2 인 경우를 붙여서 만들 수 있다. (DP[4] * DP[2])

하지만 이게 다가 아니다.

N = 4일때만 만들 수 있는 모양이 있었다. DP[2] * (4일 때만 만들 수 있는 경우 2가지) 를 더해줘야한다.

또 N = 6일때만 만들 수 있는 모양이 존재한다.

그림 실력은 양해 부탁드립니다..ㅎㅎ;

이것도 위아래가 뒤집힌 모양 까지 생각하면 총 2가지이다.

여기서 알 수 있는 것은 각 가로 길이마다 고유하게 만들 수 있는 모양이 2가지 씩 있다는 것이다.

그래서 DP[6] = DP[6-2] * DP[2] + DP[2] * (4일 떄만 만들 수 있는 경우 2가지) + (6일 때만 만들 수 있는 경우 2가지)

해서 DP[6] = 41 이다.

같은 논리로 N = 8인 경우까지만 보자면

DP[8] = DP[8-2] * DP[2] + DP[4] * (4일 떄만 만들 수 있는 경우) + DP[2] * (6일 때만 만들 수 있는 경우) + (8일 때만 만들 수 있는 경우 2가지)

이렇게 생각 할 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 30 + 5;
int DP[MAX_N];
int N;
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    DP[2] = 3;
    cin >> N;
    for (int i = 4; i <= N; i+=2) {
        DP[i] = DP[i - 2] * DP[2] + 2;
        for (int j = 4; j <= i - 2; j += 2) {
            DP[i] += DP[i - j] * 2;
        }
    }
    cout << DP[N] << "\n";
    return 0;
}

이걸 코드로 작성해주면 이렇게 된다.

N 이 홀수인 경우는 건너뛰어도 되니까 i += 2를 해줬다.