알고리즘 :: 백준 :: DP :: 11727 :: 2xn 타일링2

문제

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

문제 접근

가로의 길이가 n이므로 놓는 타일이 무엇이냐에 따라 다음 작은 문제는 n-1또는 n-2일 것이다.

• 임의의 숫자 n에 대해 경우의 수를 기록해둔다면 중복 연산을 피할 수 있으므로 DP 방법이 유효하다.
• $2\times n$ 타일을 만드는 경우의 수는 우측 맨 끝에 $1\times 2$ 타일을 2개 놓았을 때와 $2\times 1$ 타일을 1개 놓았을 경우 그리고 $2\times 2$타일을 1개 놓았을 때로 나눌 수 있다.
• $1\times 2$ 타일을 2개 놓았을 때와 $2\times 1$ 타일을 1개 놓았을 경우는 동일하다는 것을 아는 것이 핵심이다.
• 따라서 점화식은 $D(n) = D(n-1) + 2D(n-2)$이다.

코드

#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';
}

결과