[백준] 11727번: 2*n 타일링 2 [C++]

 

알고리즘 분류: 다이나믹 프로그래밍

문제 링크: https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

 

 

【 풀이 】

 

역시 다른 DP문제와 마찬가지로, 경우의 수를 계산하면서 규칙을 찾는 것이 중요하다.

2*n 직사각형을 채우는 방법의 수를 저장한 배열을 N이라고 했을 때, N[4] 까지의 값들은 다음과 같다.

1	2	3	4
1	3	5	11

 

여기서, N[n] = N[n-2]*2 + N[n-1] 이라는 점화식을 도출할 수 있다.

즉 이에 따라 12까지의 값을 나열하면 다음과 같다.

 

3	4	5	6	7	8	9	10	11	12
5	11	21	43	85	171	341	683	1365	2731

 

 

 

 

【 코드 】

 

#include<iostream>
using namespace std;

int main(void)
{
	long long int N[1001];
	int n;
	cin >> n;
	N[1] = 1;
	N[2] = 3;
	for (int i = 3; i <= 1000; i++)
		N[i] = (N[i - 2] * 2 + N[i - 1])%10007;
	cout << N[n];
	return 0;
}