[C++] 백준 11726번 문제풀이

타일링 문제는 유명해서 잘 봐둬야 한다.

이 문제를 보고 BFS를 이용하여 풀려고 했으나

시간 초과가 떴다.

그래서 DP 를 이용하였는데

위 그림을 보면 dp[n]=dp[n-1]+dp[n-2]

를 이해 하기쉽다.

이를 코드로 작성하면

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

	ios_base::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	cin >> N;
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2; i <= N; i++) {
		dp[i] =( dp[i - 1] + dp[i - 2]) % 10007;
	}
	cout << dp[N]%10007;
}