백준 2133번 타일 채우기 C++

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

 

단순한 dp문제처럼 보이지만 조금 생각해봐야 할 것이 있는 문제이다.

우선 3*2 타일은 이렇게 세 가지가 가능하고, 

1*2와 2*1 타일만 사용하기 때문에 타일의 면적은 무조건 짝수가 나온다. 그러므로 3*홀수의 타일은 불가능하다는 것을 알 수 있다.

3*3 타일은 불가능하기 때문에, 3*4 타일의 경우를 생각해보면,

일단 3*2 타일의 경우에서 각각의 타일에 3*2타일을 또 붙이는 경우

일단 이렇게 9가지가 있고, 새로운 모양이 나온다.

이런 모양이 나오는데, 위아래로 뒤집어서 이런 모양이 2개가 나온다.

그래서 3*4 타일의 개수는 11개이다.

이제 3*6 타일을 살펴보면, 

우선 이런 경우가 있다. 2칸 전의 타일에서 3가지 방법을 추가하는 경우 (dp[i-2]*3)

그리고 4칸 전부터 새로운 모양이 생긴다.

이런 식으로 타일이 추가될 때마다 새로운 모양이 계속 생기기 때문에 dp[i-2]*3 에다가

(dp[i-4]*2 + dp[i-6]*2 + .... dp[2]*2) (새로운 모양이 생기는 경우, 2를 곱하는 이유는 새로운 모양을 뒤집을 수 있기 때문) 과 2를 더해주어야 한다. (타일이 하나도 없을 경우)

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	int dp[31] = { 0 };
	dp[2] = 3;
	dp[4] = 2 + dp[2] * 3;

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