취미로 코딩하기

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

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

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

N이 적당히 작다면 적당한 DP문제였겠지만, N이 1,000,000,000,000,000,000까지 입력이 들어오므로 일반적인 DP는 사용할 수 없을 것이다. 대신 이 문제는 점화식을 구해, 해당 점화관계를 행렬의 거듭제곱을 통해 O(lgN)의 속도로 계산하는 것으로 해결할 수 있다.

An을 N의 값이 n일 때의 답이라고 하자.

우선, N이 홀수라면 타일을 배치할 수 없으므로 0을 출력한다.

N이 0이라면 아무 타일도 배치하지 않는 하나의 경우의 수가 존재하므로 A0 = 1이다.

N이 2라면 (문제 예제에도 나와있듯이) A2 = 3이다.

N이 4 이상의 짝수라면, 두 경우를 제외하면 "전체 타일이 완전히 세로선으로 두 부분 타일링으로 나뉠 수 있는 곳" 중 가장 오른쪽 선이 존재할 것이고, 이를 바탕으로 식을 세우면 다음과 같은 식을 얻는다.

A_2k = 3 * A_2k-2 + 2 * A_2k-4 + 2 * A_2k-6 + ... + 2 * A0

여기서, A_2k와 A_2k-2를 나타내는 점화식의 차를 구하면 더 간단해진 형태의 점화식을 얻을 수 있다. 이는 직접 해보자.

위에서 얻은 점화식을 이용하여 행렬의 거듭제곱을 통한 빠른 계산을 해주자.

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

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

ll mat[2][2] = { {4,-1},{1,0} };
ll vec[2] = { 3,1 };

ll tmat[3][3];
ll tvec[3];

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

	ll N; cin >> N;
	if (N & 1) cout << 0;
	else {
		N >>= 1;
		N--;
		while (N > 0) {
			if (N & 1) {
				for (int i = 0; i < 2; i++) {
					tvec[i] = 0;
					for (int k = 0; k < 2; k++) {
						tvec[i] += mat[i][k] * vec[k];
					}
				}
				for (int i = 0; i < 2; i++) {
					vec[i] = tvec[i] % 1000000007;
				}
			}

			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					tmat[i][j] = 0;
					for (int k = 0; k < 2; k++) {
						tmat[i][j] += mat[i][k] * mat[k][j];
					}
				}
			}
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					mat[i][j] = tmat[i][j] % 1000000007;
				}
			}
			N >>= 1;
		}

		if (vec[0] < 0) vec[0] += 1000000007;
		cout << vec[0];
	}
}