[동적프로그래밍] 백준 2133번 타일 채우기 (C++)

 

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

동적프로그래밍의 문제 중 하나인 타일 채우기 문제이다.

 

해당 문제는 3*n의 벽을 타일로 채우는 경우의 수를 구하는 문제이며 내용또한 간단해 보일 수 있다.

 

앞선 [2 x n 타일링] 과 [2 x n 타일링 2] 문제를 풀었다면 비슷한 방식으로 풀 수 있다고 생각이 들 수 있다.

 

만약 풀지 못했다면 꼭 풀고 오거나, 

https://lee-soo.tistory.com/2

[다이나믹프로그래밍]백준 11726,11727번 2 x n 타일링 1,2) (C++)

 

앞선 문제에 대한 포스트에 대해 보고 오길 바란다.

 

두 문제들은 

 

해당 사진처럼 "바로 이전 dp (=i-1)"의 값에 새롭게 들어올 블록 하나만 추가한 경우 이므로 그저 dp[i-1]과

ㅇ

또한 누워있는 두가지 경우의 수를 고려하여(=i-2) dp[i-2]를 더해주어 값을 구하였다.

 

dp[i]=dp[i-1]+dp[i-2]로 말이다.

 

그렇다면 이 문제도 비슷한 과정으로 흘러갈까?

 

먼저 가장 기본적인 알아야 할 것이

3 x n 일때 2 x 1 , 1 x 2 의 블록으로만 채워야 하는데 이 때 각 블록들은 짝수이며 (=2) 만약 n이 홀수일 경우에는 절대 채울 수 없기에 0이다 ( n=3이면 넓이가 9이므로 채울 수 없음 ) 

 

그렇다면 n이 짝수인 경우에만 그림을 그려보자

기본적인 3 x 2 블록들을 그려보면

 

이렇게 3가지 경우의 수가 나오게 된다.

 

이제 n=4 인경우를 그려 볼 건데, 앞서 말한 내용을 이용하면?

 

 

이전 짝수 값에다가(=i-2) 세가지 경우의 수만 구해주면 되는 것으로 보인다

 

그렇다면 dp[i]=dp[i-2] *dp[2] 인가?

 

하지만 아쉽게도, n의 값이 커질수록 새로운 모양이 나오게 되는데 .. 바로

 

이 모양이다.

 

해당 모양은, n=4일때 해당 경우와 앞뒤를 뒤집은 경우 총 두가지가 더 생겨서 앞서 말한 dp[i-2]*dp[2]+2 = 11가지가 된다.

 

설명이 직관적으로 와닿지 않을 수 도 있다.

앞서 말한 dp[i-2] * dp[2]과정을 통해서 생길 수 있는 경우의 수 안에 해당 모양이 포함되어 있지 않아야 중복되지 않아 그대로 더해줄 수 있기 때문인데, 앞서 dp[2]의 모양들이 해당 독자적인 모양에 포함되어 있지 않기 때문에 가능하다

 

 

그렇다면.. n=6일때는 어떠할까?

먼저 똑같이 dp[i-2] *dp[2]을 진행하고 나면 먼저 33이란 값이 나오게 된다.

그럼 이제 독자적인 모양에 대해서 생각을 해보자

 

먼저 n=6일때 나올 수 있는 독자적인 모양은

해당 모양으로, n=8 , 10 , 12로 늘어나도 해당 모양은 총 2가지 ( 이것과 이것을 뒤집은 모양)밖에 안나오게 된다.

 

그럼 이거 2개만 더해주면 되는거 아닌가? 라고 생각이 드는데 미처 생각하지 못한 부분이 있을 것이다.

그건 바로 앞선 식에서 dp[i-2] * dp[2]는  dp[4] * dp[2]의 값을 한 것이고, 그걸 영역으로 보여주면

해당 4:2를 나누어서 경우의 수를 구한 것인데,, 4의 영역 내부에는 4만의 독자적인 모양이 들어가 있을 것이다.

그렇다면 뒤집은 경우는 어떻게 되는가?

 

앞선 식에서 미처 고려하지 못한 부분이 이것이다. 이걸 2*4로 나누었을 땐, 이 독자적인 칸을 생각하지 못하였다.

이것까지 더해줘야 3 x 6 타일링의 갯수가 채워지는 것이며, 해당 오른쪽 칸은 두가지 값(독자적인)만 들어가고 왼쪽은 dp[2]값만 곱해준다. 마지막으로 6만의 독자적인 값 2를 더해주게 되면

 

dp[6]= dp[4] *dp[2] + dp[2]*2 +2  = 41이다.

 

그렇다면 더 크게 나누어서 8로 가볼까?

8역시 독자적인 값은 2개

먼저 dp[6] * dp[2]를하게되면

6 x 2 안에 6에는 6의 독자적인 값이 이미 포함되어 있다.

 

그렇다면 영역을 절반으로 나누어 4 x 4를 보자

 

앞선 식 ( 6 x 2 )에서 왼쪽 영역 4를 먼저 보자, 4 x 4 일때 앞선 6 x 2과 중복되는 값이 있을까?

있다. 당연히 독자적인 값 6 과 기본적인 값들로 이루어진 식은 이미 해당 6 x 2에서 모두 계산이 된 상태이다.

그렇다면 4x4에서 주로 보아야 할 것은 오른쪽부분 4이다.

 

오른쪽 부분에서의 4는 앞선 식에서 독자적인 값만 계산되지 못했다고 볼 수 있다.

그렇다면 이 값을 따로 더해주면 된다!

 

dp[4] * 2[독자적인 값]  

 

또한 2 x 6 으로 나누어도 같다. 앞선 값들에서 유일하게 적용되지 못한 값은 2x(독자적인 값) 이므로

 

dp[2] * 2 이다.

 

그리고 마지막으로 8만의 독자적인 값 2가지를 더해주면 되는데 

 

그렇다면 3 x 8의 경우의 수는 

dp[8] =dp[6]*dp[2] + dp[4]*2 + dp[2]*2 +2= 153

 

뭔가 규칙이 보이지 않는가?

해당 블록을 2 * n-2 / 4 * n-4 / ........ / n-2 * 2 로 계속 나눈 값을 더해주는데, 처음 2*n-2에서는 dp[n-2] * dp[2]를 하고 이후 나눈 값에서는 중복되지 않기위해 dp[n-4k] 와 독자적인 값 2만을 곱해서 더해주고 있지 않은가?

 

그렇다면 점화식은 간단하다.

dp[i]=dp[i-2]*dp[2] + dp[i-4] * 2 ...... dp[2]*2 + 2

 

가 되는 것이고 이것을 c++로 변환해서 쓴다면?

#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

long dp[100001];

// long r_dp[100001];

int main()

{

    int n;

    cin >> n;

    dp[0] = 1;

    dp[1] = 0;

    dp[2] = 3;

    // for (int i = 3; i <= 30; i++)

    //     r_dp[i] = r_dp[i - 1] + r_dp[i - 2];

    for (int i = 3; i <= 30; i++)

    {

        if (i % 2 != 0)

        {

            dp[i] = 0;

            continue;

        }

        dp[i] = 0;

        dp[i] = dp[i - 2] * dp[2];

        for (int j = 0; j < i - 2; j += 2)

        {

            dp[i] += dp[j] * 2;

        }

    }

    cout << dp[n] << "\n";

}

해당 코드가 나오게 된다.

코드의 통일성을 위해 dp[0]=1로하여 마지막에 2 더해주는 것을 표현하였다.

 

 

처음에는 2 x n 타일링 값을 사용하지 않을 까 하여 값을 구해놨는데 경우의 수가 너무너무 많아지기 때문에 포기했다.