[이것이 코딩 테스트다] 바닥 공사

❓ 문제 ❓
가로의 길이 n, 세로의 길이 2인 직사각형 바닥을 (1,2) (2,1) (2,2)의 덮개로 채우는 경우의 수를 구하여라.

💯 문제 풀이 💯
점화식 a = a(i-1) + a(i-2) * 2이다.

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001];
int main() {
	int n; cin >> n;

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

	cout << dp[n];
}