[Baekjoon] 11726번: 2xn 타일링

🥅 문제

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

 

🔍 설계

직접 그려서 파악해보면, 파란색 화살표는 2*1 타일을 추가하여 만들어지고, 빨간색 화살표는 1*2 타일을 두 개 붙인 것을 추가하여 만들어진다.

 

즉, dp[i] = dp[i-1] + dp[i-2]라는 것을 알 수 있다.

 

👊 풀이

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

int n;
vector<int> dp(1001);

int main(void)
{	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
		dp[i] %= 10007;
	}
	cout << dp[n] << "\n";
	return 0;
}