[BOJ] 11726번 | 2xn 타일링 (C++)

🔗문제 보러가기

11726번: 2×n 타일링

 

🧑🏻‍💻풀이 과정

$n=1$부터 하나씩 그려보면, 피보나치 수열의 규칙이 생깁니다.

 

$n=1$과 $n=2$를 베이스로 삼아, $n=3$부터는 $n-2$와 $n-1$을 가지고 조합해 나가는 방식이다 보니, 피보나치 수열과 같은 규칙이 생기는 것 같네요.

 

---

✏️ 소스 코드 및 결과 

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

void SetFastIO()
{
	ios::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
}

int main()
{
	SetFastIO();
	int N;
	cin >> N;

	vector<int> dp(N);
	dp[0] = 1;
	
	if (N >= 2)
		dp[1] = 2;

	for (int i = 2; i < N; i++)
		dp[i] = (dp[i - 2] + dp[i - 1]) % 10007;
	cout << dp[N - 1];
	
	return 0;
}