[2133] C++ : 타일 채우기

 

문제 링크

2133번: 타일 채우기

 

한창 dp 문제에 빠져있을 때 푼 문제중 하나이다. 다른 문제들과는 다르게 생각을 좀 오래 한 문제 중 하나인 것 같다. 2Xn 문제 유형은 자주 풀어봐서 쉬웠는데 3XN 형태는 처음이라서 처음에 내가 생각했던 것과 다르게 예외 케이스가 있었던 것 같다. 

성능 요약

메모리: 2020 KB, 시간: 0 ms

문제 설명

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

입력

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

출력

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

풀이

일단 이런 종류의 타일 문제가 나오면 그려보는 것이 가장 좋은 방법이다. 

- n = 1일 때는 가능한 경우의 수가 없음을 알 수 있다. 
- n = 2일 때는 아래 세가지 모습밖에 존재하지 않아서 3이다. 

- n = 3일 때에도 가능한 경우의 수가 없다. ==> 더 생각해보면 n = 5, 7, 9 등도 2x1, 1x2 타일로 채울 수 없음을 알 수 있다. 그래서 우리가 생각해야하는 건 짝수의 경우밖에 없다. 

- n = 4 일때부터 갑자기 경우의 수가 많아진다. 기본적으론 n=2일 때의 조각들을 하나의 블럭처럼 생각하여 조합할 수 있다. 그럼 3x3 = 9이다. 이렇게 만든 조각은 아래와 같이 생겼다. 

처음에는 이 경우의 수 밖에 고려를 하지 못했었다. 하지만, 예시에서도 볼 수 있듯이 2개의 경우의 수가 더 있다. 

그래서 n = 4인 경우는 11임을 알 수 있다. 

- n = 6일 때 부터는 슬슬 그리기 귀찮아 졌다. 그래서 간단하게 숫자로 표현해 보았다. 2X3 블럭은 총 3개의 경우의 수가 있으니 3으로 표현을 하고 4X3 블럭 중 특이한 케이스 ( 바로 위 사진의 블럭) 는 2가지 경우의 수가 있으니 2라고 표현했다. 

그렇게 하면 아래와 같은 규칙을 찾을 수 있다. ( 문제를 해결할 당시 그냥 그림판에 끄적였던 거라 깔끔하지 않은 점 이해 부탁한다 )

 

위의 식에서 규칙을 찾을 수 있다. 바로 직전 부분은 X3 으로 들어가고 그 전전부터는 X2를 한 수를 더하면 찾을 수 있다는 것을 알 수 있다. 그래서 점화식을 간단하게 써보면 n번째 (이때, n은 짝수, 2이상) 를 구하려면 arr[n-2] * 3와  arr[n-k] *2 (k 는 짝수, n-k > 0) 를 더하면 된다. 코드로 간단하게 만들면 아래와 같다.

#include<iostream>

using namespace std;

int main()
{
	int n;
	cin >> n;

	long long arr[31] = { 0 };
	arr[2] = 3;
	for (int i = 3; i <= n; i++)
	{
		if (i % 2 != 0)
			continue;
		for (int j = i - 2; j >= 2; j -= 2)
		{
			if (j == i - 2)
				arr[i] += arr[j] * 3;
			else
				arr[i] += arr[j] * 2;
		}
		arr[i] += 2;
	}
	
	cout << arr[n] << '\n';
}