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

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

2133번: 타일 채우기

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

int N;
int dp[31];
bool flag = false;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    dp[0] = 1, dp[2] = 3;
    cin >> N;
    if(N%2) flag = true; //홀수 거르기
    for(int i=4; i<=N; i+=2)
    {
        dp[i] = dp[i-2] * dp[2];
        for(int j=i-4; j>=0; j-=2)
        {
            dp[i]+=(dp[j]*2); //직전 고유 문양 2 * 남은 칸
        }
    }

    cout << (flag == true ? 0 : dp[N]);
}

 

꽤나 복잡하다고 느꼈던 DP 문제이다.

해당 문제에서 N이 홀수일때는 타일을 맞춰서 넣는게 불가능하다.

따라서 홀수일때 답은 0으로 고정이다.

 

따라서 가장 작은 짝수인 N=2를 기준으로, 타일의 기본 문양은 3가지이다.

이를 기준으로 계속해서 타일의 조합을 구하게 된다.

 

N=4일때를 보면 먼저 절반씩 나눠 본다.

그러면 3x2 의 형태가 2개가 되고, 이는 앞서 구한 dp[2](N=2)의 조합형태가 된다.

따라서 dp[2]*2로 일단 9개를 가지게 된다.

그리고 직접 타일을 직접 그리다 보면 고유한 문양 2개를 확인할 수 있다.

이 고유 문양 2개를 더해주면 dp[4]=11이 된다.

 

N=6일때를 보면 짝수의 경우만 보기 때문에 4/2로 나눠준다.

dp[4]의 경우와 dp[2]의 경우를 앞서 구했기 때문에 두 값을 곱하여 나오는 조합을 구해준다.

여기서 33의 경우의 수를 우선 구할 수 있다.

그리고 dp[4]일때의 고유 문양을 활용할 수 있다.

이 고유 문양 2개와 남은 공간을 활용하여 (6-4=2) 또 새로운 조합을 구할 수 있다. [dp[2]*2]

또한 마찬가지로 dp[6]일 때도 고유 문양 2개가 존재한다.

따라서 총 합은 33 + 6 + 2 = 41개가 된다.

 

여기서 중복되는 것은 1. 매번 고유문양 2개가 존재하고, (+2 고정)

2. 앞선 고유문양과 남은 칸에 오는 경우의 수가 존재하고, (2 * 남은칸)

3. 처음 경우의 수를 구하는 경우이다. (칸을 나누고 각 칸을 곱하여 경우의 수 구하기)

 

1번의 경우는 매 계산이 끝난 후 2를 따로 더해줘도 되지만, dp[0]을 1로 놓고 2의 계산식에서 활용할 수 있다.

 

2번의 경우 i는 4부터 시작하기에 j도 i-4부터 시작한다.

이는 4부터 고유문양을 가지기 때문에 4부터 시작하는 것이다.

6의 경우 직전 고유문양 활용시 4칸을 먹기에 4를 빼주고, 남은 2칸의 경우의 수 (dp[j=2])와 고유 문양 2를 곱해준다.

8의 경우 4일때 고유문양 활용시 dp[4]*2, 6일때 고유문양 활용시 dp[6]*2 이렇게 2번 더해줘야 한다.

이를 식으로 보면 j은 i=4부터 시작하여 2씩 줄어드며, 이때마다 dp[i]+=dp[j]*2를 해주면 된다.

j>=0까지하는 이유는 매 도형마다 새로운 고유문양 2개가 고정적으로 생기는데, 이를 편하게 더해주기 위함이다.

(dp[0]=1 초기화의 이유)

 

3번의 경우는 간단하게 dp[i-2]*dp[2]이다.

초기화값으로 선언했던 dp[2]=3을 활용하여 2를 뺀 나머지 칸의 경우의 수와 기본 모양 3가지를 의미하는 dp[2]의 값을 곱하여 경우의 수를 구해준다.

dp[6]의 경우로 볼 때, 나누는 것을 (2,4 / 4,2) 이렇게 2가지 경우로 나눌 수 있지만 2가지 모두 행하게 된다면 중복값이 발생하기 때문에 1가지 케이스만 고려한다.

처음에 이를 생각하지 못하여 전부 나눠주고 다 더해주는 형식으로 했다가 중복이 엄청 발생하여 틀렸었다.