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

1. 문제 링크

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

2718번: 타일 채우기

2. 문제 개요

4*N 크기의 타일을 2*1, 1*2 크기의 도미노로 완전히 채우려고 한다. N이 주어졌을 때, 타일을 채우는 방법의 개수를 출력하는 프로그램을 작성하시오.

 

3. 문제 힌트

   N-1번 열까지는 전부 다 채웠고, N번 열을 채울 건데, 채우기 전에 N번째 열은 어떤 상태가 될 수 있을지 생각해보기.

   상태들을 정리 해 두고, N번째 열에서 각 상태가 되려고 할때 N-1의 어떤 상태에서 올 수 있는지 생각해보기.

 

4. 문제 풀기

top-down방식인 재귀로 구현했습니다.  (3)번에 있듯이, n-1.... 0 까지는 모두 다 채워져 있다고 가정합니다.

FIg 1. 왼쪽에서 부터 dp[n][0] , dp[n][3], dp[n][6] , dp[n][9], dp[n][12]를 의미함.

위의 그림1은 가능한 상태들입니다.

 

Fig 2.존재할 수 없는 상태 중 1개

 

존재할 수 없는 상태인 이유는 저런 식으로 배치한다고 가정해봅시다. 그럼 n-2..... 1, 0까지 갔을 때 빈칸들이 다 메꿔지지 않습니다.

 

 

dp [n][0] 은 무엇인지 생각해봅시다. 

dp [n-1][state]를 사용해서 dp [n][0]을 구해야 합니다.

dp [n-1][state]에서 n-1번째 열에 타일을 뒀을때 n번열이 모두 가득 찬 경우입니다. ( 상태 0과 상태 15는 논리적으로 같습니다.)

 

그래서 예를 1개 들어보겠습니다.

dp [n][3]를 구해보도록 하겠습니다.

Fig 3.dp[n][3] = dp[n-1][0] 성립

dp [n][3]을 만들 수 있는 1가지 경우입니다.

dp [n-1][0]인 상태에서 적절하게 타일을 놓아서 dp [n][3]과 같은 경우를 만들어 낼 수 있습니다.

 

 

Fig 4. dp[n][3] = dp[n-1][0] 안되는 경우

 

이렇게 놓아도 되지 않는가?라고 이야기할 수도 있겠지만, 'n-1'열에만 놓아야 합니다. 위의 그림은 'n'열에 놓고 있기 때문에 적절하지 않습니다.

Fig 5. dp[n][3] = dp[n-1][12] 성립

그림 5와 같은 경우 또한 'n-1'번째 열에 블록을 적절히 놓아서 dp[n][3]과 같은 상태를 만들어 내는 경우입니다.

따라서 dp[n][3] = dp[n-1][0] + dp[n-1][12]가 됩니다.

 

예는 상태 3번만 들었지만, 이와 같이 각 상태에 대해 이전 값을 사용하여 구해주면 됩니다.

참고로 상태 1번은 n-1이 아닌 n-2에서도 만들 수 있다는 점!!

 

5. 코드

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

int dp_table[501][16];

int dp(int cur, int state)
{
	//base
	if (cur < 0)	return 0;
	if (cur == 0)	return state == 0;	//텅텅 비어야 1가지 가능.
	int &cache = dp_table[cur][state];
	if (cache != -1)	return cache;

	switch (state) {
		case 0:
			cache = dp(cur - 1, 0) + dp(cur - 2, 0) + dp(cur - 1, 3) + dp(cur - 1, 9) + dp(cur - 1, 12);
			break;
		case 3:
			cache = dp(cur - 1, 0) + dp(cur - 1, 12);
			break;
		case 6:
			cache = dp(cur - 1, 9);
			break;
		case 9:
			cache = dp(cur - 1, 0) + dp(cur - 1, 6);
			break;
		case 12:
			cache = dp(cur - 1, 0) + dp(cur - 1, 3);
			break;
	}
	return cache;
}


int main()
{
	int t;
	scanf("%d", &t);

	memset(dp_table, -1, sizeof(dp_table));
	while (t--){
		int n;
		scanf("%d", &n);
		printf("%d\n", dp(n, 0));
	}

	return 0;
}

6. 결과 사진

 

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