[백준/BOJ] 11726 - 2×n 타일링 (c++) (DP)

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

이 문제의 푸는 방법을 먼저 말하자면 피보나치 배열과 똑같은 답이다.

 

이유는 

 

n = 1일때 아래와 그림과 같이 2×1 하나로 되어 결과는 1이다.

n = 2일때는 아래와 그림과 같이 2×1 2개, 1×2 2개로 조합하여 만들 수 있기에 결과는 2이다.

n = 3일때는 두가지 경우로 나눌 수 있는데

 

왼쪽의 그림은 n = 2의 그림에 단지 2×1 1개만 붙인 것이다.

 

 

 

 

왼쪽의 그림은 n = 1의 그림에 단지 1×2 2개만 붙인 것이다.

 

 

 

위에 그림에서 보이다시피 n = 3의 경우의 수는 n = 2일때 경우의 수랑 n = 1일때 경우의 수를 더한값이다.

 

즉

n = 1 -> 1

n = 2 -> 2

n = i (i>=3) -> n = i - 1의 경우의 수 + n = i - 2의 경우의 수

이다.

---

소스코드

 

#include <iostream>

using namespace std;

int n, dp[1001];

int main() {
	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];
}