[👊DP뿌시기 #3] (BOJ 14852) 타일 채우기 3

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

14852번: 타일 채우기 3

 

문제

2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

 

---

접근법

저번 문제와 비슷하지만 1X1 피스가 생기면서 개복잡해졌다.

 

N=1인 경우와 N=2인 경우는 위 그림처럼 각각 2개, 7개씩 나온다.

 

N=3인 경우는 일단

N=2에 가로1 피스를 더한 경우와 N=1에 가로2 피스 중 (2x1, 1x1) 제외한 피스를 붙인 경우를 더한다.

 

2x1과 1x1의 경우, N=2인 경우에 중복되는 것이 있으므로 생략한다.

 

여기서 골때리는 거는 저번 문제 처럼 특수도형이 있다는 것이다.

 

따라서, D[3] = D[2]*2 + D[1]*3 + D[2] 이다.

 

D[4]인 경우도 마찬가지로

위처럼 구할 수 있다.

따라서, 해당 문제의 점화식은 다음과 같이 정의 가능하다

 

D[n] = D[n-1]*2 + D[n-2]*3 + 2*{D[n-3] + ... + D[0]}가 된다. (D[0] = 1)

 

그래서 코드를 다음과 같이 작성했다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
#define MAX 1000001
#define ll long long

ll dp[MAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    
    cin >> n;

    dp[0] = 1; // 특수모양 추가용
    dp[1] = 2;
    dp[2] = 7;
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] * 2 + dp[i - 2] * 3;
        for (int j = i - 3; j >= 0; j--) {
            dp[i] += (dp[j] * 2) % 1000000007;
        }
    }

    cout << dp[n]%1000000007 ;
    
    return 0;
}

 

근데 시간초과가 계속 발생한다.

 

그 이유는 dp[i] += (dp[j] * 2) 때문이다.

dp[j]를 다 2씩 곱해서 더하는 과정이 반복되므로 메모이제이션을 사용해서 해결할 수 있다.

 

DP[n][1] 은 DP[n-3]부터  DP[1]까지의 합을 저장한다.

따라서, DP[N][0] = DP[N-1][0]*2 + DP[N-2][0]*3 + DP[N][1]*2 이다.

 

그러면 DP[N][1]은 어떻게 구할까?

 

 

일단 다음과 같이 표를 정리하자

 

여기서 DP[0][0]과  DP[2][1]을 더한 값이 DP[3][1] 이라고 하자.

왜냐하면 DP[2][1]은 DP[-1]까지 더한 값이므로 DP[0]을 더하면 DP[0]까지 더한 값이 된다.

 

따라서, 위 점화식 처럼 *2를 해서 더하면 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
#define MAX 1000001
#define ll long long

ll dp[MAX][2];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    
    cin >> n;

    dp[1][0] = 2;
    dp[2][0] = 7;

    dp[2][1] = 1;
    
    for (int i = 3; i <= n; i++) {
        dp[i][1] = (dp[i - 3][0] + dp[i-1][1]) % 1000000007;
        dp[i][0] = (dp[i - 1][0] * 2 + dp[i - 2][0] * 3 + dp[i][1] * 2) % 1000000007;
    }

    cout << dp[n][0] % 1000000007;
    
    return 0;
}