[Algorithm]Baekjoon 14852번 :: 타일 채우기 3

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

14852번: 타일 채우기 3

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int MOD = 1000000007;
int n;
long long dp[1000001] = { 0 };
long long sum[1000001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    dp[0] = 1;
    dp[1] = 2;
    dp[2] = 7;
    dp[3] = 22;
 
    sum[0] = 1;
    for (int i = 1; i <= 3; ++i)
    {
        sum[i] = dp[i] + sum[i - 1];
    }
 
    for (int i = 4; i <= n; ++i)
    {
        dp[i] = (2 * dp[i - 1]) % MOD +
            (3 * dp[i - 2]) % MOD +
            (2 * sum[i - 3]) % MOD;
 
        dp[i] %= MOD;
        sum[i] = (sum[i - 1] + dp[i]) % MOD;
    }
 
    cout << dp[n];
}

 

타일채우기 문제인데, 기본예제문제인 2xN 타일링에서 1*1짜리 블럭이 추가된 문제이다.

일단 기본적으로 맨 앞에 2*1짜리를 세워놓으면 dp[n-1]만큼의 경우의수가 추가되는데, 이 때 이 문제에서는 1*1짜리블럭이 존재하기 때문에 2*1짜리에 세워놓을수있는게 2개가 된다. 

그렇기 때문에 2 * dp[n-1]를 더해준다.

 

그다음 맨 앞에 2*2만큼의 독립적인 형태를 세울경우 dp[n-2]만큼의 경우의 수가 추가되는데, 2*2만큼의 독립형태 개수가 총 3개가 된다. (1*2 2개, 위 1*2 1개, 아래 1*1 2개 , 위 1*1 2개, 아래 1*2 1개)

그렇기 때문에 3* dp[n-2]를 더해준다.

 

여기까지는 이전에 타일링문제를 풀어봤다면 쉽게 생각할 수도 있을 것이다.

다만 이 다음이 문제인데, 1*1짜리로 인한 특별한형태가 생기는 경우이다.

이 1*1짜리블럭이 추가됨으로써 특별한 형태가 생기고, 그렇기 때문에 누적값들을 계속 들고있어야 한다.

1*2짜리를 엇나가게 쌓으면 모서리에 1*1짜리들만 넣을 수 있는형태의 블럭모양이 나오는데 바로 이 형태가 특별한 형태이다.

 

이 형태들은 2*3, 즉 n이 3이상일때부터 발현되는 형태이고, 각 n값마다 특별한형태가 1개씩 생기기때문에 누적값들을 계속 들고있어야 한다는 것이다.

 

n값이 5라고 가정하면, 맨처음 두가지 경우 말고도 (2 * dp[n-1] + 3* dp[n-2] ) 특별한형태가 3, 4 두개가 존재한다.

즉, 2*3크기의 특별한형태를 맨 앞에 두면, dp[n-2]를 추가로 더해야 할 것이다.

그리고 2*4크기의 특별한형태를 맨 앞에 두면, dp[n-1]을 추가로 더해야 한다.