[BOJ 14852 // C++] 타일 채우기 3

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

 

이번에 볼 문제는 백준 14852번 문제인 타일 채우기 3이다.

문제는 아래 링크를 확인하자.

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

14852번: 타일 채우기 3

적당히 큰 n에 대하여, n번째 열까지 타일을 채우는 경우의 수는 다음의 네 가지 경우가 있다.

1. n-1번째 열까지만을 보았을 때 타일이 (잘리지 않고) 완전히 채워져있는 경우. 각 경우마다 2가지의 n번째 열까지 타일을 채우는 경우의 수를 얻을 수 있다.

2. n번째 열의 첫번째 행에 행방향 두칸 블럭이 놓이는 경우. 이 경우, n-1번째 열의 첫 행이 비고 두 번째 행만 채워진 경우의 수만큼 n번째 열까지 타일을 채우는 경우의 수를 얻을 수 있다.

3. n번째 열의 두번째 행에 행방향 두칸 블럭이 놓이는 경우. 2와 비슷하게 처리할 수 있다.

4. n번째 열의 두 행 모두 행방향 두칸 블럭이 놓이는 경우. 이는 n-2번째 열까지만을 보았을 때 타일이 완전히 채워져있는 경우의 수와 같은 만큼의 경우의 수를 얻을 수 있다.

 

마찬가지로, n번째 열까지 n번째 열의 한 칸을 제외한 모든칸을 채우는 경우의 수에 대한 식 또한 세울 수 있다.

 

위의 점화관계들을 이용하여 n을 하나씩 증가시키며 경우의 수를 구해나가자.

 

아래의 코드에서 A는 n번째 열까지 모두 채우는 경우의 수, B는 n번째 열까지 n번째 열의 두번째 행을 제외한 모든 칸이 찬 경우의 수, C는 n번째 열까지 n번째 열의 첫번째 행을 제외한 모든 칸이 찬 경우의 수를 나타낸다.

 

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

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

ll A[1000001], B[1000001], C[1000001];

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

	A[1] = 2, A[0] = B[1] = C[1] = 1;
	int N; cin >> N;
	for (int i = 2; i <= N; i++) {
		A[i] = (2 * A[i - 1] + B[i - 1] + C[i - 1] + A[i - 2]) % 1000000007;
		B[i] = (A[i - 1] + C[i - 1]) % 1000000007;
		C[i] = (A[i - 1] + B[i - 1]) % 1000000007;
	}

	cout << A[N];
}