타일 채우기 (feat. 백준, 2133번)

타일 채우기
https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, dp[16]{1};
    cin >> N;
    if(N & 1 == 1){
        cout << 0;
    }
    else{
        for(register int i = 1, j; i <= N / 2; ++i){
            dp[i] += dp[i - 1] * 3;
		    for (j = 2; j <= i; j++)
			    dp[i] += dp[i - j] * 2;
        }
        cout << dp[N / 2];
    }
	return 0;
}
// *&)*@*

 

반응형

 

1. 오랜만에 dp 유형의 문제입니다.
2. 타일의 3 X N 중 N이 홀수인 경우는 무조건 0이 출력됩니다. (문제의 힌트 그림 참조)
3. 또한 N이 짝수일때마다 그 이전 짝수의 3배가 추가된만큼 경우의 수가 늘어납니다.
4. 따라서 이를 이용하여 dp 식을 유도하면 되겠습니다.