백준저지 2133번 타일 채우기 문제 풀이

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

백준저지 2133번 문제 타일 채우기 문제 풀이입니다.

전형적인 dp문제로 부분문제로 나누어서 풀 수 있습니다.

저 같은 경우는 dp[len][state]로 나누었는데 len 이전까지의 타일의 모든 칸은 이미 채워졌다고 가정하고 len번째 column(열)의 타일은 state 형태로 채워져 있다고 부분문제를 정의했습니다.

새로 행은 3칸이 있으므로 총 2^3로 8가지의 상태가 있을 수 있고, 이를 비트마스크로 표현했습니다.

기존 모양에서 가장 왼쪽 칸을 모두 채우는 경우의 수를 따져보면 위와 같이 나타납니다.

위의 경우를 구현한 코드는 다음과 같습니다.

 

#include <bits/stdc++.h>
using namespace std;

int dp[31][8]; //dp[len][state]
int main() {
    int n;
    cin >> n;
    dp[0][0] = 1;
    for (int i=0; i < n; i++) {
        auto& c = dp[i];
        auto& n = dp[i+1];
        n[4] += c[0];
        n[1] += c[0];
        n[7] += c[0];
        
        n[0] += c[1];
        n[6] += c[1];
        
        n[5] += c[2];
        
        n[4] += c[3];
        
        n[0] += c[4];
        n[3] += c[4];
        
        n[2] += c[5];
        
        n[1] += c[6];
        
        n[0] += c[7];
    }
    
    cout << dp[n][0] << endl;
	return 0;
}