2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
가로의 길이가 n
이므로 놓는 타일이 무엇이냐에 따라 다음 작은 문제는 n-1
또는 n-2
일 것이다.
n
에 대해 경우의 수를 기록해둔다면 중복 연산을 피할 수 있으므로 DP 방법이 유효하다.#include <iostream>
#include <cstring>
using namespace std;
static int n = 0;
static int cache[1001];
int solve(int num) {
if (num == 0 || num == 1) return 1;
if (cache[num] > 0) return cache[num];
// 2xn 타일을 만드는 경우의 수는 (1x2 2개 또는 2x2 1개) + (2x1 2개)이다.
return cache[num] = (solve(num - 1) + 2 * solve(num - 2)) % 10007;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
memset(cache, 0, sizeof(cache));
cout << solve(n) << '\n';
}