[BOJ] 백준 11726번 - 2×n 타일링

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

11726번: 2×n 타일링

 

대표적인 DP 문제이다.

 

우선 문제를 보는 순간 점화식으로 표현될 것 같다는 생각이 든다. 2*n 크기의 직사각형을 1*2, 2*1 두 종류의 타일로 채울 때, 모든 경우는 2가지로 나눌 수 있다.

1. 가장 왼쪽 타일이 2*1 타일로 시작하는 경우
2. 가장 왼쪽 타일이 1*2 타일로 시작하는 경우 -> 1*2 타일은 위아래로 붙어서 2*2 형태로만 존재할 수 있다.

 

타일의 종류는 2종류만 존재하므로 가장 왼쪽 타일은 2*1타일 혹은 1*2타일이어야만 한다. 1번 경우를 보면 가장 왼쪽에 위치하는 2*1 타일 하나를 제외하고 보면 오른쪽 부분은 2 * (n-1) 크기의 직사각형이 된다. 이 직사각형을 채우는 방법의 수는 f(n-1) 이다.

2번 경우는 1*2 타일은 2개씩 붙어서 2*2 형태로 존재해야만 하므로 가장 왼쪽의 2*2 모양의 타일을 제외하고 보면 오른쪽 부분은 2 * (n-2) 크기의 직사각형이고 이를 채우는 방법의 수는 f(n-2) 이다. 이를 통해 아래 점화식을 얻을 수 있다.

 

f(1) = 1

f(2) = 2

f(n) = f(n-1) + f(n-2). (n>2 일 때)

 

이는 피보나치 수열을 이루고, 점화식을 이루는 문제는 DP 를 통해 해결 가능하다. 

#include <iostream>
using namespace std;

int dp[1001] = {0};
int Tiling (int n);

int main (){
    int n;
    cin>>n;
    Tiling(n);

    cout<<dp[n];

    return 0;
}

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

    return dp[n];
}