백준 / 다이나믹 프로그래밍 / 11727번 / 2 x n 타일링 2 / C++

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 

2

예제 출력 1 

3

예제 입력 2 

8

예제 출력 2 

171

예제 입력 3 

12

예제 출력 3 

2731

 

#include <iostream>
using namespace std;

const int N = 1e3 + 1;
const int divisor = 1e4 + 7;
int arr[N] = {0, 1, 3};

int tiling(int n) {
	for(int i=3; i<=n; i++) {
		arr[i] = (arr[i - 2] * 2 + arr[i - 1]) % divisor;
	}
	
	return arr[n];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	
	cout << tiling(n) << '\n';
	
	return 0;
}

---

전역변수들에 대한 설명은 아래의 포스팅을 참조바란다.

2021.08.17 - [ALGORITHM/백준] - 백준 / 다이나믹 프로그래밍 / 11726번 / 2 x n 타일링 / C++

백준 / 다이나믹 프로그래밍 / 11726번 / 2 x n 타일링 / C++

 

이번에는 1과 달리 규칙찾기가 조금 더 어려웠다.

하나씩 그려가면서 규칙을 찾기엔 많은 시간이 소요될 것이고, (2 x 2) 타일이 추가 되었으니 

n일때 n-2도 고려하면서 규칙성을 찾아보았다.

 

일단 n이 3일때 n이 2일때와의 차이는 2x1 타일이 하나 더 붙는다는 것이다.

따라서 n-1이 n이 되기위해선 한가지 방법이 존재한다.

 

n이 1일때와 3일때의 차이는 옆에 2 x 2공간이 더 붙는다는 것이다.

그러면 2 x 2를 만들 수 있는 방법은 몇가지일까?

1x2타일 2개나, 2x1타일 2개나 2x2타일 1개로 만들 수 있다.

결국 총 3가지 이다.

하지만 2x1타일 두개 붙일때를 생각해보면, n-1일때의 방법과 겹친다는것을 알 수가 있다.

겹치기때문에 한가지 방법을 제외해주면 2가지이다.

 

따라서 arr[n] = arr[n-1] + arr[n-2]*2로 나타낼 수 있다.

이것만 구하면 출력만 하면 되는 문제이다.