BaekJoon 11727번: 2xn 타일링 2(C++)

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

11727번: 2×n 타일링 2

풀이법

1) DP를 활용하여 푸는 문제이다. 점화식을 구하는 것이 중요하다.

2) a1=1, a2=3, a3=5, a4=11 임을 시도한다면 알 수 있다.

기존의 배열에 2x1을 더하는 것과, 1x2 혹은 2x2를 더하는 경우를 나누어서 생각해 주면 된다.

arr[n-1]에 2x1을 더하는 경우에 arr[n]을 만들 수 있다.

arr[n-2]에 1x2를 더하는 경우 또한 arr[n]을 만들 수 있다.

arr[n-2]에 2x2를 더하는 경우에도 마찬가지로 arr[n]을 만들 수 있다.

최종 점화식은 arr[n]=arr[n-1]+arr[n-2]*2 가 된다.

 

#include<iostream>
#include<algorithm>
#define NUM 10007
using namespace std;
int n;
int arr[1001];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	arr[1] = 1;
	arr[2] = 3;
	arr[3] = 5;
	arr[4] = 11;
	for (int i = 5; i <= n; i++)
	{
		arr[i] = (arr[i - 1] + arr[i - 2] * 2)%10007;
	}
	cout << arr[n];
}