[Algorithm]Baekjoon 11727번 : 2xn 타일링 2

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

11727번: 2×n 타일링 2

int dpArray[1001];
 
int dp(int n)
{
    for (int i = 3; i <= n; i++)
    {
        dpArray[i] = (dpArray[i - 1] + (dpArray[i - 2]) * 2) % 10007;
    }
 
    return dpArray[n];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    dpArray[1] = 1;
    dpArray[2] = 3;
    
    cin >> n;
 
    cout << dp(n) << endl;
}

 

타일링문제에 대해 감을 좀 잡았다.

타일의 종류대로 왼쪽을 채우고 남은 공간에 대해 dp를 더해주면 된다.

이 문제같은 경우, 타일의 종류는 2x1, 1x2, 2x2 총 세종류의 타일이 있는데 (세로,가로 순)

왼쪽을 채울 수 있는 경우는 2x1을 하나 붙이던가, 1x2를 2개붙이던가, 2x2짜리 하나를 붙이던가다.

 

2xn의 공간에 대해서, 2x1을 왼쪽벽면에 붙이면 남은 공간은 2x(n-1)의 공간이다. 즉 f(n-1)

2xn의 공간에 대해서, 1x2 2개를 왼쪽벽면에 붙이면 남은 공간은 2x(n-2)의 공간이다. 즉 f(n-2)

2xn의 공간에 대해서, 2x2짜리 1개를 왼쪽벽면에 붙이면 남은공간은 2x(n-2)의 공간이다. 즉 f(n-2)

 

그렇기 때문에 점화식은 f(n) = f(n-1) + f(n-2) * 2  가 된다.