BOJ 2133번 :: 타일 채우기

#문제

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

입력

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

출력

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

 

#작성 코드

#include <cstdio>

int memo[31];

int tile(int x){
	if(x==0) return 1;	// 아무 것도 놓지 않는 것은 한가지 
	if(x==1) return 0;
	if(x==2) return 3;
	if( memo[x]!=0 ) return memo[x];
	int result = tile(x-2)*3;
	for(int i=4; i<=x; i+=2){
		result+=2*tile(x-i);
	}
	return memo[x]=result;
}

int main()
{
	int n;
	scanf("%d", &n);
	printf("%d\n", tile(n));
	return 0;
}

##

n이 홀수일 때는 절대 타일을 채울 수 없다.

n이 짝수일 때

-> 0일때는 1가지. 아무것도 놓지 않는 것도 한가지의 방법이다.

-> 2일때는 3가지.

-> 4일때는 2일때의 3가지에 2가지를 추가하게된다.

     ex)

 

+) N이 조금 더 큰 수일 경우에 2차원 dp를 사용하면 +2*tile(n-4)+2*tile(n-6)+... +2*tile(0)의 계산을 더 빠르게 수행할 수 있지 않을까 해서 2차원 dp를 사용해서도 풀어보았다.

#include <iostream>

int memo[31][2];
// memo[n][0]에는 3xn타일을 칠하는 경우의 수 저장.
// memo[n][1]에는 3x(0) ~ 3x(n-2)타일을 칠하는 경우의 수의 합 저장.

int tile(int x){
	memo[0][0] = 1;
	memo[1][0] = 0;
	memo[2][0] = 3;
	memo[2][1] = 1;
	if( x%2!= 0) return 0;
	for(int i=4; i<=x; i+=2){
		memo[i][1] = memo[i-2][1] + memo[i-2][0];
		memo[i][0] = 3*memo[i-2][0] + 2*memo[i-2][1];	
	}
	return memo[x][0];
}

int main(){
	int n;
	std::cin>>n;
	std::cout<<tile(n)<<'\n';
	return 0;
}

note