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

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

2133번: 타일 채우기

좀 검색해보니까 다른 방식으로 많이 풀었길래 한 번 포스팅 해봅니다

 

 

[문제 요약] 3xN의 빈 공간을 (2X1, 1X2) 타일로 채운다. 

 

[아이디어 생각 과정]

일단, 문제를 보고 바로 떠오른 세 가지가 있는데

1) DP 문제 

2) N이 홀수일 땐 불가능

3) 어떤 칸이든, 1X2 타일이 "반드시" 들어감

 

그리고 DP 규칙을 찾으려고 연습장에 이리저리 끄적여 보면서 경우의 수를 생각해 봤다. 

진짜 이상한 방식도 많이 생각했는데, 결국 예전에 풀었던 2XN 타일링 방식이 생각이 났고, 거기서 추가해보자는 생각을 했다.

 

2XN 타일링

문제에선 주어진 타일이 1과 2밖에 없다는 점을 이용해 1을 추가하거나, 2를 추가하거나 하는 식으로 DP를 세운다. 

이 부분을 응용했는데, 아이디어는 다음과 같다. 

 

= > 3XN 타일링은, 2XN 타일링의 가로형을 기본으로 1X2 타일을 아래 끼우냐, 위에 끼우냐의 판단이다. 

 

예시)

3XN 의 N이 2일 때  : 3

DP[i-1] + 1 -> 3이 된다.

근데 위를 보면 알 수 있는 사실이,

1x2 타일을 2개 썼을 땐 위아래 구분 없이 하나의 3x2 타일이 되고, 

2x1을 2개 썼을 땐 위 아래 위치에 따라 2개의 모양으로 나뉜다는 것이다. 

 

여기까지 OK

 

3XN 의 N이 3일 때  : 답(0) -> DP(4)

N = 3 일 때, 실제 답은 0이지만, 내가 세운 점화식을 쓰려면 DP[i-1] + DP[i-2] = 4가 나와야 한다.

DP[2]에서 구한 경우의 수 ( 위아래를 모두 구분 했었음 ) + 가로 한칸 타일을 일단 옆에 하나 둔다(위아래 x)

DP[1] (1X2 타일) + (2X1타일 2개) 로 가로 폭을 맞춰 준다. 

 

 홀수는 무조건 0이 된다 -> 성립하지 않는다.

1X2타일과 2X1 타일로 N의 구색만 맞춰 준다.

 

그럼 홀수번쨰 항에선, 위아래 구분을 추가해줘야 하는 타일이 4개 생긴다. 

 

3XN 의 N이 4일 때  : 11

DP[4] = DP[2] + 2 * DP[3]

N=3 (N이 홀수) 일 때, 위나 아래에 (1X2) 타일을 추가해 줘야 하는 경우를 4개 만들어줬다. 

N=4 (다음 짝수) 에선, (2x1)을 하나 추가해주고, 위나 아래 구분까지 해주면 된다.

N=2 (전 짝수) 의 경우에는 (1X2)타일 3개를 추가하는 수 밖에 없기 때문에 그대로 더해준다.

 

따라서 점화식은 

N%2==1 : DP[N-2] + DP[N-1]

N%2==0 : DP[N-2] + 2 * DP[N-1]

가 된다. 

 

타일을 조금 조합해 보면 결국 문제가 되는 경우는 

이런 경우 때문인 걸 알 수 있는데, 2XN 타일 기법을 쓰면 저걸 구할 수 있단 것도 생각해 낼 수 있다. 

그럼 어떻게 구현하냐 ? 인 건데, 

2X1 타일은 짝수 항에서 홀수개로 있을 수 없다.   는 점을 이용해서 생각해낼 수 있었다 ㅇㅇ. 그냥 옆에만 둔다! 는 개념 ! 

 

[코드]

#include<iostream>

using namespace std;


int N;

int main() {
	cin >> N;
	if (N % 2) {
		cout << 0;
		return 0;
	}
	int DP[31];
	DP[1] = 1;
	DP[2] = 3;
	for (int i = 3; i <= N;i++) {
		if (i % 2)
			DP[i] = DP[i - 2] + DP[i - 1];
		else
			DP[i] = DP[i - 2] + DP[i - 1] * 2;
	}
	cout << DP[N];
}

 

그렇습니다~~

 

글솜씨가 부족해서, 궁금한 점이 있으면 댓글 남겨주세요