2133 타일 채우기

백준 2133 타일채우기 https://www.acmicpc.net/problem/2133

<유사문제>
1793 타일링 https://www.acmicpc.net/problem/1793
11726 2xn 타일링 https://www.acmicpc.net/problem/11726
11727 2xn 타일링2 https://www.acmicpc.net/problem/11727


유사문제는 모두 2xN에 관해서라 쉽게해결된다.
이 문제는 3xN크기의 벽을 채우는 경우의 수를 구하는 문제이다.

하지만 타일링문제에서 마지막부분을 채우는 경우를 나눠 생각했던것처럼 마지막 부분에 신경을 쓰고 앞의 부분에 조금 신경쓰면 해결할 수 있다.

마지막 부분을 채우는 경우는 총 세가지로 나뉠 수 있다.

해당 경우를 각각 0번, 1번, 2번이라 하고 이 세가지 경우를 각각 따져보도록 하자

1. <0번 경우>

0번경우에서도 다음과같이 2가지로 나뉠 수 있다. 

0번형태의 경우가 다시 되풀이 되거나 완전 빈틈없는 형태가 될 수 있다. 완전 빈틈없는 형태가 되면 그 앞에는 0번, 1번, 2번 어느것이 오든 만족한다.

따라서 $DP[N][0]=2*DP[N][0] + DP[N][1] + DP[N][2]$가 되겠다.  

2. <1번 경우>

1번경우도 마찬가지이다.

$DP[N][1] = DP[N][0] + 2*DP[N][1] + DP[N][2]$가 된다.

3. <2번 경우>

완전 빈틈없는 형태이기 때문에 앞에 무엇이 오든 상관이없다.

$DP[N][2] = DP[N][0] + DP[N][1] + DP[N][2]$

모든 점화식을 구했으니 초기값을 넣고 N일때 0번, 1번, 2번경우를 다 더해주면 모든 경우의 수를 구할 수 있다.

#include <cstdio> int dp[31][3]; int main(){     int N;     scanf("%d", &N);     dp[2][0] = dp[2][1] = dp[2][2] = 1;     for (int n = 4; n <= N; n += 2){         dp[n][0] = 2 * dp[n - 2][0] + dp[n - 2][1] + dp[n - 2][2];         dp[n][1] = dp[n - 2][0] + 2 * dp[n - 2][1] + dp[n - 2][2];         dp[n][2] = dp[n - 2][0] + dp[n - 2][1] + dp[n - 2][2];     }     printf("%d\n", dp[N][0] + dp[N][1] + dp[N][2]);     return 0; } Colored by Color Scripter

cs