2×n 타일링

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

198757

77351

57441

36.867%

문제

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

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

입력

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

출력

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

#include<iostream>

using namespace std;

int N;
long D[1001];
long mod = 10007;

//2×N 크기의 직사각형을 1×2와 2×1 타일을 이용하여 채울 수 있는 경우의 수를 구하는 문제

int main()
{
	cin >> N;

	D[1] = 1; //2x1의 경우의 수는 1가지
	D[2] = 2; //2x2의 경우의 수는 2가지

	for (int i = 3; i <= N; i++)
	{
		//DP 점화식
		D[i] = (D[i - 1] + D[i - 2]) % mod;
	}

	cout << D[N];
}