boj, 백준) 2133. 타일 채우기 ( C / C++)

1. 문제 링크

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

2133번: 타일 채우기

2. 문제 개요

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

 

3. 문제 힌트

 손수 경우의 수를 찾아보기.

숫자가 늘어날때 어떤 규칙이 있는지 찾아보자.

 

4. 문제 풀기

우선 주어진 타일로 (2x1, 1x2) 1열을 만들 수는 없다. 적어도 2 열전에서 만들어야 한다. 그리고 홀 수열은 만들 수 없다.

2칸을 만들 수 있는 3가지 경우

따라서 dp[n] = 3*dp [n-2]가 성립한다. (그냥 오른쪽에 갖다 붙인다고 생각.)

 

그런데 진행하다 보면 4칸을 만들 수 있는 경우의 수 가 발생한다.

도중 발생하는 경우

위의 왼쪽 그림을 보자, 상하 대칭으로 4칸을 만들 수 있는 경우가 2가지가 생긴다. 따라서, 반복문을 사용해서 4칸을 만드는 경우의 수를 추가해야 한다. 6칸도 상하 대칭으로 2개가 있다.

따라서 반복문을 사용해서 계산 해주어야 한다. 코드를 보면 이해가 될 것이라고 생각한다.

 

bit연산을 사용해서 상태를 나타내어 봤으나 결국 이런 반복문 구조로 다시 돌아왔다. 따라서 비트 마스크는 필요 없다고 생각한다.

 

5. 코드

#include <cstdio>
#include <algorithm>
using namespace std;

int n;
int dp[31];
int main(void)
{
	scanf("%d", &n);
	dp[0] = 1;
	dp[2] = 3;
	for (int i = 4; i <= n; i++)
		if (i % 2 == 0){
			dp[i] = 3 * dp[i - 2];

			for (int j = i - 4; j >= 0; j = j - 2)
				dp[i] += 2 * dp[j];
		}
	
	printf("%d", dp[n]);

	return 0;
}

 

지적, 댓글 언제나 환영입니다~