#11726 2xn 타일링

# 문제

# 입력 및 출력

# 풀이

예전에 푸는 방법은 찾았는데 이해를 못해서 그냥 북마크 해두고 나중에 이해될때 다시 풀려고 했다

전에 01타일 문제를 풀다가 이문제와 내용이 비슷해서 이제는 이해될 것 같아서 다시 풀어봤다

n>=3 일때 항상 타일은 ㅣ타일 한개와  ㅡㅡ 타일 두개로 끝남

따라서 2xn 타일링 방법은 총 두가지임

1) n-1 타일링 방법에 l 타일을 더하는 방법

2) n-2 타일링 방법에 ㅡㅡ 타일을 더하는 방법

 

따라서 점화식은 dp[n] = dp[n-1] + dp[n-2]가 됨

 

#include <iostream>
using namespace std;
int dp[1001];

int main() {
	int n;
	cin >> n;
	dp[1] = 1, dp[2] = 2;
	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
	}
	cout << dp[n];
}

n이 46부터는 int 범위를 넘어서 값이 터지기 때문에 배열에 넣을때부터 10007로 나눈 값으로 넣어줌