[알고리즘] 백준 11727 - 2×n 타일링 2

1. 문제

https://www.acmicpc.net/problem/11727

2. 입력/출력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

3. 풀이

11726 - 2×n 타일링의 변형문제이다.
11726번과 마찬가지로 DP를 이용해 풀 수 있는데, 점화식만 문제에 맞게 고쳐주면 풀 수 있다.

4. 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(0);

	int n;
	cin >> n;

	int dp[1001];

	dp[1] = 1;
	dp[2] = 3;

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

	cout << dp[n] % 10007;
}