백준 2133 타일 채우기

도형에다가 dp 문제이기 때문에 도형을 일단 하나하나 그려보면서 규칙성을 찾고자 했다.

3X4사이즈의 벽을 그리던 와중 3X2벽에서 나온 타일의 패턴을 이용할 수 있겠다는 생각이 들어서 바로 3 * 3 = 9 가지구나! 라고 생각하고 코드를 구현했는데 당연히 틀렸다. 왜냐하면 3X2의 패턴말고 추가 패턴이 2가지 더 나오기 때문이다 (빨간 동그라미 친 패턴)
풀겠다는 의지를 가지고 3X8까지 그려본 결과 각 단계별로 추가 패턴은 2개가 나온다는 것을 확인했다.

3X6의 패턴을 파악하던중 중복이 나올 수 있다는것을 알게되었고 중복을 피하고자 하는 방법을 찾기 시작했다. 패턴을 케이스 별로 나누어 생각하는것인데 첫번째 케이스의 경우 이전과 같은 논리로 3X2의 패턴경우의 수 * 3X4의 패턴경우의 수  를 해주면 된다. 

 

두번째 케이스에서 부터 중복을 신경써주어야하는데 중복을 피하는 방법은 당연히 케이스 1의 모양이 안나오면 되는것이고 안나오게 하려면 벽의 오른쪽 부분이 3X2의 패턴으로 채워지면 안된다. 따라서 3X2의 패턴이 아닌 다른 패턴으로 채워져야 한다는것인데 그것이 바로 3X4의 패턴중 추가패턴임을 알 수 있다. 따라서 두번째 케이스는  3X4의 추가패턴 * 3X2의 패턴경우의 수 이다.

 

3X6의 패턴 경우의 수 = (3X2의 패턴경우의 수 * 3X4의 패턴경우의 수) + (3X4의 추가패턴 * 3X2의 패턴경우의 수) +2
마지막 +2는 3X6의 추가패턴이다

 

여기까지의 설명으로 점화식을 파악할 수 있는 사람은 아래 설명을 더는 읽지 않아도 된다. 필자는 3X6만으로는 점화식을 반만 생각해 낼 수 있었기 때문에 3X8의 케이스까지 파악한 후 점화식을 찾아냈다.

 

3X8 패턴 구하기

3X8의 경우는 세가지 케이스로 나눌 수 있다.
각 케이스 계산 과정은 그림에 쓰여있음 (글씨가 난리나긴했지만 알아볼 수 있다)

1. 3X2벽과 3X6벽

2. 3X4 벽 두개

3. 3X6벽과 3X2벽

1번 케이스는 3X2의 패턴경우의 수 * 3X6의 패턴경우의 수  

2번 케이스는 3X4의 패턴경우의 수 * 3X4의 추가패턴의 수  (중복을 생각해줘야함!)

3번케이스는 3X6의 패턴경우의 수 * 3X2의 패턴경우의 수 (중복을 생각해줘야함!)

1번 케이스를 통해 3 * dp[i-2] , 2번 케이스를 통해 2*dp[i-4], 3번케이스를 통해 2 * dp[i-6]이라는 점화식을 도출 할 수 있었다. 

점화식

dp[N] = 3 * dp[N-2] + 2 * dp[N-4] + 2 * dp[N-6] + ... + 2 * dp[0]

 

#include <iostream>
#include <algorithm>

using namespace std;

int n;
//dp[수의 길이][마지막으로 끝나는 수]
int dp[31];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    //벽이 홀수일 경우 채우지 못함
    if(n % 2 == 1){
        cout << 0;
        return 0;
    }
    //마지막 벽의 추가도형을 위해 dp[0]은 1로 초기화
    dp[0] = 1;
    dp[1] = 0;
    dp[2] = 3;
    for(int i=4; i<=n; i = i+2){
        dp[i] = 3 * dp[i-2];
        for(int j = i-4; j>=0; j= j-2){
            dp[i] += 2 * dp[j];
        }
    }
    
    cout << dp[n];
    
    return 0;
}