[2133] 타일 채우기

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

2133번: 타일 채우기

문제

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

입력

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

출력

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

코드

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int N;
int dp[31];

int main(void){
	cin >> N;


	dp[1] = 0;
	dp[2] = 3;
	dp[3] = 0;
	dp[4] = 11;
	
	for(int i=5; i<=N; ++i){
		if(i %2 == 1){
			dp[i] = 0;
		}

		// 전 타일의 끝지점 집중
		else{
			for(int j = 3; j <= i/2; ++j){
				dp[i] += dp[i-(j-1)*2]*2;
			}
			dp[i] += dp[i-2]*3 + 2;
		}
	}

	cout << dp[N];
}

꽤 까다로운 dp 문제이다.

3*N의 타일을 채우는데 내가 생각한 관점과 구글에 올라온 관점이 달라 두가지 모두 설명해볼려 한다.

첫번째 관점은, 타일의 끝부분에 집중하는 것이다.

마지막에 오는 타일의 종류에 따라 점화식이 결정된다.

예를들어, 3*4 타일을 채울 때, 3*2 타일을 채우는 방식 3가지가 끝에올 수 있기 때문에 dp[i-2]*3 에다가 3*4를 채우는 특별한 모양 2가지를 더해 11가지가 된다. (특별한 모양에 대한 그림은 링크로 첨부하겠다.)

또, 3*6타일을 채울 땐 3*4때와 마찬가지로 dp[i-2]*3에다가 3*4를 채울 때 쓴 특별한 모양 2가지로 인해 dp[i-4]*2를 더해주고 또 특별한 모양 2가지가 나오니 2를 더한다. 그래서 dp[i-2]*3 +  dp[i-4]*2 +2를 해주어 41가지가 된다.

이 점화식을 일반화 해서 세운 코드가 위의 코드이다.

 

또 구글링해서 찾은 방식은 다르다. 내가 생각한 관점보다 더 명확한거 같다.

경우의 수를 이용한 방식인데 설명하면 너무 기니 링크를 첨부하겠다.

https://yabmoons.tistory.com/536

[ 백준 2133 ] 타일 채우기 (C++)

이 분이 경우의 수를 이용해 잘 설명하신 것 같다.