취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2718번 문제인 타일 채우기이다.
문제는 아래 링크를 확인하자.

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

간단한 점화관계를 찾아 문제를 해결해보자.

4행K열의 타일에 대하여 다음과 같은 수열을 정의하자:

A1234[k]: 주어진 타일을 도미노로 모두 채울 경우의 수

A12[k]: 주어진 타일을 마지막 열의 3번 행과 4번 행의 칸을 제외한 모든 칸을 도미노로 채울 경우의 수

A23[k]: 주어진 타일을 마지막 열의 4번 행과 1번 행의 칸을 제외한 모든 칸을 도미노로 채울 경우의 수

A34[k]: 주어진 타일을 마지막 열의 1번 행과 2번 행의 칸을 제외한 모든 칸을 도미노로 채울 경우의 수

A41[k]: 주어진 타일을 마지막 열의 2번 행과 3번 행의 칸을 제외한 모든 칸을 도미노로 채울 경우의 수

이 때, 4행K열 타일의 마지막 열을 어떤 식으로 채우느냐를 생각하는 것으로 다음과 같이 점화식을 세울 수 있다:

A12[i] = A1234[i - 1] + A34[i - 1] // 1행과 2행에 걸친 2x1 도미노를 배치 or 1행과 2행에 각각 1x2 도미노를 배치
A34[i] = A1234[i - 1] + A12[i - 1] // 위와 같은 방식
A23[i] = A1234[i - 1] + A41[i - 1] // 위와 같은 방식
A41[i] = A23[i - 1] // 위와 같은 방식, 4행과 1행에 동시에 걸치게끔 2x1 도미노를 놓을 수는 없음에 유의
A1234[i] = A1234[i - 1] + A12[i - 1] + A34[i - 1] + A23[i - 1] + A1234[i - 2] // 1x2 도미노를 배치하는 경우들을 생각해보면 어렵지 않게 떠올릴 수 있을 것이다.

위의 점화식을 이용해 문제를 해결하자.

A13 또는 A24와 같은 수열은 정의하지 않았는데, 이와 같은 경우는 존재하지 않기 때문이다. A13과 같은 모양의 이전 단계는 A24이어야 하고 A24와 같은 모양의 이전 단계는 A13이어야 하므로 초기상태에서 도달할 수 없음을 관찰하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int T;
ll A12[22], A23[22], A34[22], A41[22], A1234[22];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	A1234[0] = 1;
	A12[1] = 1, A34[1] = 1, A23[1] = 1, A1234[1] = 1;
	for (int i = 2; i < 22; i++) {
		A12[i] = A1234[i - 1] + A34[i - 1];
		A34[i] = A1234[i - 1] + A12[i - 1];
		A23[i] = A1234[i - 1] + A41[i - 1];
		A41[i] = A23[i - 1];
		A1234[i] = A1234[i - 1] + A12[i - 1] + A34[i - 1] + A23[i - 1] + A1234[i - 2];
	}

	cin >> T;
	while (T--) {
		int x; cin >> x;
		cout << A1234[x] << '\n';
	}
}