[백준 14852번] 타일 채우기 3 (C++)

문제링크 : https://www.acmicpc.net/problem/14852

14852번: 타일 채우기 3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

const int MOD = 1000000007;
int N;
ll dp[1000001], sum[1000001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    
    dp[1]=2; //N은 1인 경우
    dp[2]=7; //N은 2인 경우
    sum[2]=1; //

    for(int i=3; i<=N; i++)
    {
        sum[i] = (dp[i-3] + sum[i-1]) % MOD;
        dp[i] = (dp[i-1]*2 + dp[i-2]*3 + sum[i]*2) % MOD;
    }

    cout << dp[N];

    return 0;
}

 

현재 타일 기준 다음 타일은 2*1 타일만큼의 공간이 추가된다.

이에 대한 경우의 수는 2가지이며(2*1, 1*1 + 1*1), 이에 따라 dp[i]=dp[i-1]*2이라는 점화식을 알 수 있다.

 

현재 타일 기준 다다음 타일은 2*2 타일만큼의 공간이 추가된다.

이에 대한 경우의 수는 3가지이며(2*1 + 2*1, 2*1 + 1*1 + 1*1, 1*1 + 1*1 + 2*1), 이에 따라 dp[i] = dp[i-2]*3이라는 점화식을 알 수 있다.

 

이후 타일들에 대해서는 고유한 형태가 2가지가 추가된다.

따라서 2*(dp[i-3] + dp[i-4] + .....dp[0])의 값을 추가로 가지게 된다.

해당 합에 대해서는 따로 sum 배열을 추가하여 dp[i-3]의 값과 sum[i-1]의 값을 더해 누적합을 따로 구하도록 해주었다.

이후 dp[i-1]*2 + dp[i-2]*3을 구할때 추가로 2*sum[i]를 하여 누적합 * 고유문양 2가지에 대해 추가로 더해주었다.

 

dp 초기값으로 직접 카운팅을 해보면 dp[1]=2, dp[2]=7을 구할 수 있기에 이를 초기값으로 두고 반복문은 i=3부터 시작한다.

이 경우 누적합을 위해 선언한 sum 배열이 직전 누적합에 추가로 더해주는 형태이기 때문에 sum[2]에 대해 1로 초기화를 해준다. (i=3부터 시작)