[C++][백준] 11726번 2×n 타일링 :: seoftware

 

---

 

문제접근

---

다이나믹 프로그래밍, DP

가로의 길이가 n인 직사각형을 타일로 채우는 방법은 가로의 길이가 n-1인 직사각형을 타일로 채운 상태에서 2*1 타일을 1개 붙이는 방법과 가로의 길이가 n-2인 직사각형을 타일로 채운 상태에서 1*2 타일을 2개 붙이는 방법이 있다.

따라서 가로의 길이가 n인 직사각형을 타일로 채우는 관계식은 다음과 같다.

( 가로의 길이가 n인 직사각형을 타일로 채우는 방법의 수 )

= ( 가로의 길이가 n-2인 직사각형을 타일로 채우는 방법의 수 )

+ ( 가로의 길이가 n-1인 직사각형을 타일로 채우는 방법의 수 )

 

소스코드

---

#include <iostream>
using namespace std;

int dp[1001];

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