백준 2133번: 타일 채우기

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

2133번: 타일 채우기

 

 

 

 

 

문제

 

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

 

 

 

입력

 

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

 

 

 

출력

 

첫째 줄에 경우의 수를 출력한다.

 

 

 

 

 

3x1 크기의 벽을 채우는 방법은 존재하지 않는다.

 

3x2 크기의 벽을 채우는 방법은 총 3가지가 있다.

3x3 크기의 벽을 채우는 방법은 존재하지 않는다.

 

3x4 크기의 벽을 채우는 방법은 총 11가지가 있다. (3x3+2)

 

3x5 크기의 벽을 채우는 방법은 존재하지 않는다.

 

3x6 크기의 벽을 채우는 방법은 총 41가지가 있다. (11x3+3*2+2)

 

이때 주의할 점은 n이 2씩 증가할 때마다 새로운 경우의 수가 2개씩 추가된다.

 

 

 

 

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

 

 

 

 

코드

 

#include <stdio.h>

int main(){
	int n;
	scanf("%d",&n);

	int dp[31]={ 1, 0, };

	dp[2]=3;

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

	printf("%d\n", dp[n]);
}