#2133: 타일 채우기

백준 2133번: 타일 채우기

문제:

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

입력:

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

풀이:

• 이 문제는 #11726: 2×n 타일링과 #11726: 2×n 타일링 2의 응용 문제라고 할 수 있다. 이 문제는 바텀업 방식으로 아래서부터 위로 경우의 수를 쌓아 올리면서 마지막에 n까지 도달하는 방식을 이용해야 된다. 우선 가로 길이가 홀수인 경우는 칸이 홀수개 있으므로 무조건 경우의 수가 0일 수 밖에 없다. 짝수 칸은 길이가 2인 경우에는 나오는 모양의 경우의 수가 3가지이며 그 다음부터는 경우의 수가 2개씩 늘어난다. 즉, 4칸인 경우에 새로운 2가지 경우가 생기고 6칸인 경우에 또 2가지 경우가 생긴다. 따라서 4칸인 경우에는 총 11가지 경우가 생긴다. 그 이유는 4칸인 경우는 2칸 2칸인 경우 3*3과 4칸인 경우에 추가로 생긴 2가지가 있어서 11가지가 나온다.
• 우선 첫번째 for문에서는 이번 칸이 되기 위해 2칸을 추가한 경우이다. 3*dp[i-2]인 이유는 이번에 생긴 2칸의 3가지 경우의 수를 이전에 모든 경우의 수와 곱해주기 때문이다.
• 두번째 for문에서는 앞서 말한 2가지 경우가 추가 된 경우를 추가하는 연산을 해준다. 첫번째 for문에서는 2칸인 경우의 수를 구했다면 이번에는 4부터 n까지의 경우의 수를 모두 합해준다고 생각하면 된다. 마찬가지로 2*dp[i-j]인 이유는 이번에 생긴 j칸이 2가지 경우의 수를 추가로 갖고 있으면 그것을 j만큼 전에 있던 경우의 수와 곱해주면 j칸의 총 경우의 수가 나온다.

코드:

#include <iostream>

using namespace std;

int main(){
	int n, dp[31] = {};
	//입력
	cin >> n;
	//Base case 값 초기화
	dp[0]=1;
	dp[2]=3;
	//4에서부터 n까지 바텀업 방식으로 경우의 수 쌓아 올라감
	for(int i = 4; i <= n; i+=2){
		dp[i] = 3*dp[i-2]; //2칸이 추가 된 경우
		for(int j = 4; j <= i; j+=2){
			dp[i]+=2*dp[i-j]; //4, 6, 8, .... n칸이 추가 된 경우
		}
	}
	//출력
	cout<<dp[n];
}