백준 14852. 타일 채우기3

14852.타일 채우기3

14852번: 타일 채우기 3

---

입력

첫째 줄에 N이 주어진다.

---

풀이

• 2*N 크기의 벽을 2*1, 1*2, 1*1 크기의 타일로 채우는 경우의 수를 구해야한다.
• 처음에 f(n) = f(n-1)*2 + f(n-2)*3 과 같은 점화식을 생각하여 다이나믹 프로그래밍으로 풀이하려 하였다.
• 하지만 1*1타일이 있기 때문에 길이가 3이상인 경우에서 새로운 경우가 등장한다.
• 따라서 기존의 경우들의 합을 따로 기록하여, 이용하는 방식을 추가하여 풀이했다.
• 다음은 코드이다.

#include <iostream>
#include <algorithm>

#define MOD 1000000007

int N;
long long dp[1000001][2];

int main()
{
	std::cin >> N;

	dp[0][0] = 1;
	dp[1][0] = 2;
	dp[2][0] = 7;
	dp[3][0] = 22;
	dp[0][1] = 1;
	dp[1][1] = 2;
	dp[2][1] = 8;
	dp[3][1] = 24;

	for (int i = 4; i <= N; i++) {
		dp[i][0] = (dp[i-4][1] * 2 + dp[i - 3][1] * 2 + dp[i - 2][0] * 3 + dp[i - 1][0] * 2) % MOD;
		dp[i][1] = (dp[i][0] + dp[i - 2][1]) % MOD;
	}

	std::cout << dp[N][0];

	return 0;
}