[2133] 타일 채우기

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

이 문제의 핵심은 맨 위칸 혹은 맨 아래칸이 전부 2 * 1의 타일로 채워졌을 때 입니다. 물론 2 * 1 타일 개수는 2개 이상일 때!

2개 일 때 2개! 3개일 때도 2개, 4개일 때도 2개 !!

그러므로 점화식은 아래와 같습니다!

    for(int i = 3; i <= n; i++){
        dp[i] += dp[i - 2] * 3;
        
        for(int j = 4; j <= i; j += 2) dp[i] += dp[i - j] * 2;
    }

위의 점화식은 2칸일 때 3가지의 경우가 존재하므로 !

아래 점화식은 위에서 설명한 경우 입니다.!

풀코드입니다.

#include <cstdio>
#define MAX_SIZE 31
 
int dp[MAX_SIZE];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    dp[0] = 1;
    dp[1] = 0;
    dp[2] = 3;
    for(int i = 3; i <= n; i++){
        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;
}