[백준] 11726: 2xn 타일링

문제

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

풀이

가장 오른쪽에 올 수 있는 타일의 종류는 2가지
D[n] = D[n-1] + D[n-2]

D[0]은 아무 타일도 넣지 않은 1가지 경우 가능 -> D[0] = 1
타일을 음수 개수 선택은 불가하므로 n < 0 일때 D[n] = 0;
D[2] = 1 (1 + 0)

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

vector<int> d(1000001, 0);

int DP(int n)
{
	if (n < 0)
		return 0;

	if (n == 0)
		return d[n];

	if (d[n] > 0)
		return d[n];

	d[n] = (DP(n-1) + DP(n-2)) % 10007; // 10007을 여기서 나눠줘야 틀리지 않음

	return d[n];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	d[0] = 1;

	int Num;
	cin >> Num;

	cout << DP(Num);
}