[DP] 2133번 타일 채우기

2133번 타일 채우기

 

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

 

문제

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

 

입력

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

 

출력

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

 

예제 입력

2

3

4

5

 

예제 출력

3

11

41

153

 

해결방법

문제의 조건을 찾아 해결하는 DP 문제이다

참고 블로그 : https://mizzo-dev.tistory.com/entry/baekjoon2133

 

 

⭐️ 솔루션 ⭐️

일단 3xn 타일에서 n이 홀수인 경우는 타일을 만들 수 없다

짝수인 경우에 대해 점화식을 만들어야 한다

 

짝수의 타일의 경우는 n칸의 상태로만 만들 수 있는 특수 케이스가 존재한다

아래와 같이 2의 경우는 3개이고 나머지 경우는 2개가 존재한다

 

맨 우측을 3 x 2 ~ 3 x n-2 타일의 특수케이스를 배치하고 나머지의 경우의 수를 구해야한다

그리고 자신의 특수케이스도 존재하므로 +2 를 더해준다

 

 

 

소스코드

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

int n;
int d[31];

void dp(){
    if(n%2 == 0){
        d[2] = 3;
        
        for(int i=4; i<=n; i+=2){
            d[i] = 2;
            
            for(int j=2; j<i; j+=2){
                int _case = j==2 ? 3 : 2;
                
                d[i] += (d[i-j] * _case);
            }
        }
    }
    
    cout << d[n] << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    dp();
    
    return 0;
}