문제 링크

😜 코드 설명

전형적인 DP 문제여서 고민없이 접근하였다.
1x2, 2x1 타일밖에없기 때문에
n번째 타일에서는

n-2번에서 구성했던 타일에서 1x2타일들을 추가하고
n-1번에서 구성했던 타일에서 2x1타일들을 추가하면 완성된다.

즉 점화식은 dp[n] = dp[n-2] + dp[n-1] 이 되는 피보나치 수열이다.

😜 소스 코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int dp[1001];
int main() {
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
	int n;
	cin >> n;
	int answer = 0;
	for (int i = 3; i <= n; i++) {
		dp[i]=(dp[i - 2] + dp[i - 1])%10007;
	}
	cout << dp[n]%10007;




	return 0;
}