[25411633] 2×n 타일링 - 20200118(3)

문제 

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

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

 

풀이

n의 크기를 키워가며 방법의 수를 구하다 보면 피보나치 수의 규칙을 찾을 수 있다.

3번째 이후부터  Fn = Fn-1 + Fn-2 규칙을 적용할 수 있다.

따라서 0,1,2,3 번째까지의 vector는 초기화를 해준다.

그리고 vector의 크기가 기하급수적으로 커지는 것을 막기 위해 최종적으로 구해야하는 수인 2xn 크기의 직사각형을 채우는 방법의 수를 10007로 나눈 나머지를 저장한다. 

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int N;
vector <long long> num;

int square(int a) {
	if (a == N + 1)
		return 0;
	else {
		if (a == 0 || a == 1 || a == 2 || a == 3)
			num.push_back(a);
		else
			num.push_back(num[a - 1] + num[a - 2] % 10007);
	}
	
	square(a + 1);
	return 0;
}

int main() {
	cin >> N;
	
	square(0);
	
	cout <<  num[N] % 10007;

	return 0;
}