[백준문제풀이] 2133 타일 채우기

 

풀이일시 : 2020-08-09

​

 

문제 :

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

​

 

입력 :

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

​

 

출력 :

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

​

 

풀이 :

가장 마지막에 오는 타일을 생각했을 때 나타나는 경우의 수는 세 가지이다. (그 이전 갯수는 N-2개)

또한 4개이상일 때부터 2의 배수가 될때마다는 고유한 모양이 2개씩 나타난다.

D[i] = 3*D[i-2] + (2*D[i-4] + 2*D[i-6] + 2*D[i-8] + .... + 2*D[0])

 

아래는 DP에 대한 포스팅이다. 이의 알고리즘으로 풀이했다.

dbstndi6316.tistory.com/35?category=953970

[개념정리] DP 동적프로그래밍

 

#include <iostream>
using namespace std;
int d[1001];

int dp(int x) {
	if (x == 0) return 1; //못채우는경우
	if (x == 1) return 0; //채울 수 있는 타일이 없다.
	if (x == 2) return 3; //2일때는 3가지 경우의 수
	if (d[x] != 0) return d[x];
	int result = 3 * dp(x - 2); //점화식 분할 part.1
	for (int i = 3; i <= x; i++) { //4개일때부터 짝수개에는 경우가 두가지씩 더들어간다
		if (i % 2 == 0) //짝수개 조건에만
			result += 2 * dp(x - i); //점화식 분할 part.2
	}
	return d[x] = result; //result를 return 해준다.
}

int main() {
	int x;
	cin >> x;
	printf("%d", dp(x));
}
​

​