백준 2133번 - 타일 채우기

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

문제를 접근한 방법은 다음과 같다.

먼저 홀수 개 일때는 타일을 만들 수 가 없다.

다음으로 2개씩 타일이 늘어날 때마다 이전 타일에서 규칙적으로 늘어나는 타일이 있다.

 

 

 

그림을 보면 위의 3개의 3x2 타일이 옆에 붙을 수 있다.

 

 

 

그림을 보면 위의 2개의 3x4 타일이 옆에 붙을 수 있다.

 

 

길이가 2가 늘어날때 3개의 타일이 옆에 붙을 수 있고 4가 늘어날때 2개의 타일이 옆에 붙을 수 있다고 생각하며

다음과 같이 점화식을 세워봤다.

dp[i] = dp[i - 2] * 3 + dp[i - 4] * 2;

하지만, 위의 점화식처럼 소스를 제출했더니 계속해서 fail이 됐다.

뭐가 문제인지 고민하다가 3x4에서 끝나는 것이아니라 3x6, 3x8 타일에서도 새로운 타일이 계속해서 만들어지는 것을 알게됐다.

 

위의 그림은 3x6의 타일 2개가 새로 생성된 모습이다.

처음에는 가로가 2인 타일과 가로가 4인 길이의 타일이 붙으면 모두 포함된다고 생각했지만

위의 그림에 표시된 부분처럼 이렇게 이어져있는 부분은 포함되지 않는 것이다.

 

왼쪽 그림은 아래가 연속해서 붙어있는 모습이고 위에서는 길이가 3x2인 타일 두개가 붙어있는 모습이다.

그리고 위의 그림은 기존의 3x2의 타일과 3x4의 타일의 조합으로는 만들 수 없는 새로운 3x6의 타일이다.

 

그러므로 길이가 2씩 늘어날때마다 2가지 경우가 계속 추가되는 것을 반영해줘야 문제를 해결할 수 있다.

#include <iostream>
using namespace std;
 
int main() {
    
    int N;
    int dp[31] = { 1,0,3 };
    cin >> N;
    
    if (N % 2 == 0)
        for (int i = 4; i <= N; i+=2){
            dp[i]=dp[i-2]*3;
            
            for(int j=4;i-j>=0;j+=2)
                dp[i]+=dp[i-j]*2;
        }
    
    cout << dp[N] << endl;
    
    return 0;
}