BOJ 11726 2xN 타일링

boj 11726 2xN 타일링

간단한 DP 문제이다. DP가 무엇인지를 다시 생각해보면, 하위 문제들을 먼저 푼 후 그것들을 쌓아올려 주어진 문제를 해결하는 알고리즘이다. DP 문제를 풀 때 중점은 테이블을 정의해주고, 그 테이블의 제일 하위 값들이 무엇일까를 생각하며 점화식을 찾는 것이다. 먼저 테이블 설정을 해보면, D[i] = 1x2, 2x1 타일로 채우는 경우의 수 라고 정의하자. 전체 경우의 수 D[i]는 아래 그림과 같이 맨 끝의 한 칸을 1x2 타일이 채우는 경우와 맨 끝의 두 칸을 2x1 타일 2개가 채우는 경우 2가지로 나뉜다. 맨 끝이 3칸이 남는 경우는 더 채우면 결국 앞의 2가지와 겹치기 때문에 생각할 필요가 없다.

그러므로 점화식을 D[i] = D[i-1] + D[i-2]로 설정하고 구현한다.

#include <iostream>
using namespace std;

int n;
int D[1005];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    D[1] = 1;
    D[2] = 2;

    for (int i = 3; i <= n; i++)
    {
        D[i] = (D[i - 1] + D[i - 2]) % 10007;
    }

    cout << D[n];
}