[C++] [DP] 백준 11725번 : 2xN 타일링

쟌쥰 2020. 2. 2. 13:27

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net

#include<iostream>
using namespace std;
int tail[1001];

int dp(int n) {
	if (n == 1)	return 1;
	if (n == 2)	return 2;
	if (tail[n] != 0)	return tail[n];
	return tail[n] = (dp(n - 1) + dp(n - 2)) % 10007;
}

int main(void) {
	int n;
	cin >> n;
	cout << dp(n) << endl;
}