[백준 2133번] [수학 / DP] 타일 채우기

Approach

문제에서 주어진 힌트를 보고 잘 생각해보면, 채우는 방법은 한번에 2칸, 한번에 4칸, 6칸, .. 2k칸이 존재한다.

그리고 2칸을 채우는 방법만 3가지이고, 나머지의 경우는 2가지 존재한다.

 

또한 한번에 2칸 채우는 것을 2번 반복한 것과, 한번에 4칸 채우는 것을 1번 반복한 것의 이후 과정은 완벽학게 동일하므로 이를 중복하여 계산하지 말고 DP로 저장해두면 계산 시간을 줄일 수 있다. (물론 n이 되게 작아서 시간 안에는 무조건 들어온다.)

 

dp[i] : i번째 칸까지 채웠을 때 3 x N크기의 벽을 채우는 경우의 수

dp[i] = dp[i + 2] * 3 + dp[j] * 2 for all j s.t j % 2 == 0 & j <= n & j > 2

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int n;
int dp[31];

int solution(int k){
    int& ret = dp[k];
    if(ret != -1) return ret;
    // Base case
    if(k == n) return ret = 1;
    else if(k > n) return ret = 0;

    int result = 0;
    result += solution(k + 2) * 3;

    for(int i = k + 4; i <= n; i += 2){
        result += solution(i) * 2;
    }

    return ret = result;
}

int main(void){
    fastio;
    memset(dp, -1, sizeof(dp));
    cin >> n;
    if(n % 2 != 0){
        cout << 0 << "\n";
    }
    else{
        cout << solution(0) << "\n";
    }
    return 0;
}