타일 채우기 3 (백준 14852)

얀녕하세요. 오늘은 타일을 채울 거예요.

문제

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

아이디어

2xN의 타일을 채우는 경우의 수를 조금 나눠봅시다.

2xi의 타일을 더 작은 2x?의 타일로 나눌 수 없는 경우, 즉 세로선으로 분할이 더이상 불가능한 경우를 완전한 조각이라고 합시다. i에 따라서 이 완전한 조각의 개수가 달라지는데, i가 2일때는 3, 아니면 다 2입니다. 2xi의 크기의 완전한 조각의 개수를 i-완전한 조각의 개수라고 합시다.

2xN은 N-완전한 조각의 개수 + 1-완전한 조각의 개수xdp[N-1]+...+N-1-완전한 조각의 개수xdp[1]이 됩니다.
이 식에 대해서 설명을 하자면 2xN의 조각에서 가장 왼쪽에 있는 완전한 조각의 크기를 기준으로 나눈 것입니다.
만약 이 값이 N이라면 그냥 한 조각을 다 채우는 것이고 i라면 가장 왼쪽에 있는 완전한 조각의 크기가 i이므로 남은 N-i는 완전한 조각에 상관없이 만들 수 있는 개수, 즉 dp[N-i]가 됩니다.

식을 정리해봅시다. 편의를 위해서 N은 3이상이라고 합시다.
N-완전한 조각의 개수 + 1-완전한 조각의 개수xdp[N-1]+2-완전한 조각의 개수xdp[N-2]+...+N-1-완전한 조각의 개수xdp[1] = 2+2xdp[N-1]+3xdp[N-2]+2xdp[N-3]+...+2xdp[1]=2+2x(dp[N-1]+dp[N-2]+dp[N-3]+...+dp[1])+dp[N-2]가 됩니다. 이때 dp[1]부터 dp[N-1]까지의 합을 sum이라고 하면 dp[N]=2+2xsum+dp[N-2]가 됩니다.

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll sum = 0, dp[1010101] = { 0 };

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    dp[1] = 2; dp[2] = 7; sum = 9;

    ll N, i;
    cin >> N;
    for (i = 3; i <= N; i++)
    {
        dp[i] = sum * 2 + dp[i - 2] + 2;
        sum += dp[i];

        dp[i] %= 1000000007;
        sum %= 1000000007;
    }

    cout << dp[N];
}

감사합니다.