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

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

예제 입력 1 

2

예제 출력 1 

2

예제 입력 2 

9

예제 출력 2 

55

 

#include <iostream>
using namespace std;

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

int tiling(int n) {
	for(int i=3; i<=n; i++) {
		arr[i] = (arr[i - 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;
}

---

일단 위에 const 변수부터 살펴보자면, 기존에 #define으로 했던것을 const형으로 바꾸었다.

const는 변하지 않는값, 즉 상수를 쓸때 사용하는데 문제에서 주어진 n의 최댓값과 나누는 수는 변하지 않으므로

const를 사용했다.

 

그리고 상수 변수의 값이 1e3, 1e7 이렇게 되있는데 e의 왼쪽은 맨앞에 오는 숫자의 수, 

e의 오른쪽은 0의 개수를 생각하면 편하다.

따라서 1e3은 1000, 1e7은 10000000이다.

 

그리고 이제 규칙성을 찾아야 하는데, 이 문제는 규칙성만 찾으면 식을 찾아서 쉽게 해결할 수 있다.

일단 세로는 2로 고정이기 때문에 오히려 규칙찾기가 쉬웠던것같다.

규칙을 찾기위한 방법이 있는지는 모르겠으나... 하나하나 n의 값을 늘려가면서 직접 그려보면서 생각해보았다.

 

그결과 n이 1일때부터 시작해서 n의 값을 늘려가면서 방법의 개수를 찾아보면

1, 2, 3, 5, 8, ... 와 같은 규칙성을 발견했고 n일때 n-2의 방법의 개수 + n-1의 방법의 개수라는 것을 알게되었다.

 

컴파일 시간을 줄이기 위해 구한 수는 메모이제이션 기법을 사용했으나, 입력이 여러번 들어오는 것이 아니기때문에... 큰 차이가 있을까 싶다...