알고스팟 - 타일링 방법의 수 세기 (TILING2) [C++]

 다이나믹 프로그래밍의 대표적인 문제이다. i번째 2 x 1 칸을 어떻게 채울지를 생각하면 쉽게 풀 수 있다. 2 x 1 블록 하나로 세울 경우 i - 1번까지를 채운 경우의 수와 일치하게 되고, 1 x 2 블록 두개를 세운 경우 i - 2번까지를 채운 경우의 수와 일치하게 된다. 따라서 dp[i] = dp[i - 1] + dp[i - 2] 이고, 이를 계산하면 쉽게 풀 수 있다.

 

#include <iostream>

using namespace std;

#define MAX 100
#define MOD 1000000007

int dp[MAX + 1];

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

	int C;

	cin >> C;

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

	for (int test = 0; test < C; test++) {
		int n;
		cin >> n;
		cout << dp[n] << '\n';
	}

	return 0;
}