[c++/백준] 11727번: 2×n 타일링 2*

문제 링크

11727번: 2×n 타일링 2

풀이

점화식 구하는 거 왜이렇게 어렵냐 ...

1. n이 0이면 아예 안 놓는 경우의 수 1, n이 1이면 2x1짜리 경우의 수 1이다.
   n이 3이면 아예 안 놓는 경우의 수(dp[0])에서 2x2짜리, 1x2짜리 두개 넣는 경우의 수로 2개 + 2x1짜리에서(dp[1]) 2x1짜리 놓는 경우의 수 1개 = 3이다.
2. 즉, 점화식은 dp[n] = dp[n-2]*2 + dp[n-1]이 되겠다.
3. dp[n]을 출력하면 끝.

코드

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
	int n;
	cin >> n;

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