백준 11726번: 2 x n 타일링

[문제 링크]

11726번: 2×n 타일링

---

간단한 DP 문제였다. 피보나치 수열과 비슷한(거의 같은) 점화식으로 풀 수 있다.

2 x n 타일을 채우는 경우의 수는 타일 가장 오른쪽을 세로블록 한개로 채우는 경우의 수와 가로블록 두개로 채우는 경우의 수의 합과 같기 때문이다.

따라서 점화식은 dp(n) = dp(n-1) + dp(n-2) 이며,

기저사례로 n == 1일 때 1을 반환, n == 2일 때 2를 반환하여 횟수를 카운팅 해주면 쉽게 원하는 결과를 얻을 수 있다.

---

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

int memo[1001];

int Solution(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 2;

	int& ret = memo[n];
	if (ret != -1) return ret;

	return ret = (Solution(n - 1) + Solution(n - 2)) % 10007;
}

int main(void)
{
	memset(memo, -1, sizeof(memo));
	int n;
	cin >> n;
	cout << Solution(n) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 63 day