[비트마스크/DP] 2718 타일 채우기

이 문제는 dp로도 풀수 있고 비트마스크로도 풀 수 있는 문제이다.

dp로 풀 경우에는 각 열을 증가시키면서 새롭게 나타나는 새로운 패턴을 더해주어야 한다.

dp로 푸는 방법은 이해가 잘 안가서 포기 했고, 대신에 비트마스크를 활용해서 풀었다.

http://joonas-yoon.blogspot.kr/2016/03/2718.html

이블로그에서 너무 잘 설명해 놔서 따로 설명하진 않겠다.

재귀 호출하면서 중복된 호출을 피하기 위해서 메모이제이션 까지 구현해야 하는 상당히 좋은 문제인듯하다.

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int dp[501][13]; // 현재 상태는 1100까지 가능하고 N은 대략적으로 500으로 잡음.
//시간절약하기위해서 메모화 재귀 구현
 
int f(int n, int cur) { //n은 구해야 되는 열의 크기, cur은 현재 열의 상태
    if (n<0 || (n == 1 && cur == 6)) return 0;
    if (n == 1 || n == 0) return 1;
    if (dp[n][cur]) return dp[n][cur];
 
    int ret = 0;
    switch (cur) {
    case 0:
        ret += f(n - 1, 0);
        ret += f(n - 2, 0);
        ret += f(n - 1, 3);
        ret += f(n - 1, 9);
        ret += f(n - 1, 12);
        break;
    case 3:
        ret += f(n - 1, 0) + f(n - 1, 12);
        break;
    case 6:
        ret += f(n - 1, 9);
        break;
    case 9:
        ret += f(n - 1, 0) + f(n - 1, 6);
        break;
    case 12:
        ret += f(n - 1, 0) + f(n - 1, 3);
        break;
    }
    return dp[n][cur] = ret;
}
 
 
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int temp; cin >> temp;
        cout << f(temp,0) << endl;
    }
    return 0;
}