취미로 코딩하기

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

이번에 볼 문제는 백준 15243번 문제인 Tiling이다.
문제는 아래 링크를 확인하자.

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

3xn 직사각형을 1x2 타일을 이용해 채우는 경우의 수를 묻는 문제이다.

n이 홀수이면 채워야하는 전체 칸이 총 홀수개가 되므로 어떻게 해도 직사각형을 타일을 이용해 채울 수 없다.

그렇지 않은 경우, "맨 왼쪽부터 시작해 처음으로 부분직사각형으로 끊을 수 있는 위치"가 모든 타일링에 존재한다는 점을 이용해 dp식을 세워 문제를 해결할 수 있다. 구체적인 식은 아래의 코드를 참고하자.

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

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

ll dp[501];

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

	dp[1] = 3, dp[2] = 11;
	for (int i = 3; i < 501; i++) {
		dp[i] = 2 + 3 * dp[i - 1] + 6;
		for (int k = 2; k < i - 1; k++) {
			dp[i] += 2 * dp[i - k];
		}

		dp[i] %= MOD;
	}

	int N; cin >> N;
	if (N & 1) cout << 0;
	else cout << dp[N/2];
}