[백준] 11727번 2xn 타일링 2 / C++

#문제

백준 11727번 2xn 타일링 2

#풀이

#include <iostream>

using namespace std;

long long dp[1001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	dp[0] = 1;
	dp[1] = 1;

	for (int i = 2; i <= n; ++i)
	{
		dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
	}

	cout << dp[n];

	return 0;
}

#정리

2xn 직사각형을 1x2, 2x1, 2x2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하는 문제. ‘2xn 타일링 1’ 문제에서 2x2 타일이 추가된 형태다. 세 가지 타일을 사용하는 방법으로 나누어 생각할 수 있는데, 2x1타일의 경우 ‘dp[n-1]’과 같았고, 1x2타일은 [n-2]와 같았다. 2x2타일은 1x2타일과 같았기 때문에 점화식을 다음과 같이 유도할 수 있었다. dp[n] = dp[n-1] + dp[n-2] * 2 여기서 10,007 나머지 연산을 해주고 dp에 추가하여 해결할 수 있었다.