C++:: boj 1720 < 타일 코드 >

중복한 타일은 제거해 줘야하는 문제이다. 점화식을 생각하기 어려운 문제이다.

풀이의 핵심은 전체 타일의 수열 dp, 완전 대칭인 타일의 수열 s 를 구하면 대칭을 제거한 가지수를 구할 수 있게 된다.

#include <iostream>
#include <vector>
using namespace std;
// 타일 코드
int main() {
	int n;
	cin >> n;
	vector<int> dp(31, 0), s(31, 0);
	dp[1] = 1; dp[2] = 3;
	for (int i=3; i<=30; i++) {
		dp[i] = dp[i-1] + 2 * dp[i-2];
	}
	s[1] = 1; s[2] = 3; s[3] = 1; s[4] = 5;
	for (int i=5; i<=30; i++) {
		s[i] = s[i-2] + 2 * s[i-4];
	}
    cout << (dp[n] - s[n]) / 2 + s[n];
}