(2133)(DP) 백준 타일 채우기

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

풀이

---

먼저 3xN 배열에서 N이 홀수일 경우는 2x1배열과  1x2배열의 조합으로는 채울 수 없다는 것을 알 수 있다.

그래서 3x2, 3x4, 3x6, 3x8 ....순서대로 배열을 채울 수 있는 경우의 수를 찾기로 한다.

3x2배열의 경우는 아래와 같이 3가지 경우의 수가 존재한다.  dp[2] = 3;

위의 모양을 조합해서 3x4의 배열을 채울 수 있는 경우는 3*3으로 9가지가 있는데 예외의 경우가 아래와 같이 2개 존재한다.

dp[4] = dp[2]*3 + 2(    그림 1)의 경우와 그림 2)의 경우   );

1)            ,       2)    

3x6의 배열은 

dp[6] = dp[4]*3 + dp[2]*2(위의 그림 1), 2)의 경우 2가지) + 2(    그림 3)의 경우와 그림 4)의 경우)

3)      ,    4)     

3x8의 배열은

dp[8] = dp[6]*3 + dp[4]*2 + dp[2]*2 + 2  이 성립하게 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int main() {
    int N;
    int dp[31] = { 0 };
 
    scanf("%d", &N);
 
    dp[0] = 1;
    dp[2] = 3;
 
    for (int i = 4; i <= N; i+=2) {
        dp[i] = dp[i - 2] * 3;
        for (int j = 4; j <= i; j += 2) {
            dp[i] += dp[i - j] * 2;
        }
    }
 
    printf("%d\n", dp[N]);
 
    return 0;
}