[백준]2xn 타일링2

백준저지

[2xn 타일링2]https://www.acmicpc.net/problem/11727

• 이전 2xn타일링 포스팅과 마찬가지로 DP문제이다.

• 개인적으로 이번 문제는 점화식이 제대로 안나와서 다소 많은 시간을 투자했다.

• 이번 문제를 통해 DP를 빠르게 풀기 위해서는 눈썰미가 좋거나...

• 많은 경험과 공부를 하거나...

• 필자는 본 문제를 노가다(?)를 통해서 성공 메세지를 노출시키는데 성공했다.

• 더 나은 방법이 있다면 댓글로 알려줬으면 한다.

• 추가적으로 DP에 대해 더 심도있게 공부를 해보고 다른 방법이 있다면 본 포스팅에 추가해서 

• 해결방법을 포스팅하도록 하겠다.

(cf. 고등학교때 수학좀 열심히 할껄...)

an = an-1 + 2xan-2(a1=1, a2=3)

#include <iostream>
#include <vector>

using namespace std;

int main(void) {
	int num;
	vector<int> numArr(1001, 0);
	cin >> num;

	numArr[1] = 1;
	numArr[2] = 3;

	for (int i = 3; i <= num; i++)
		numArr[i] = (2 * numArr[i - 2] + numArr[i-1]) % 10007;

	cout << numArr[num];

	return 0;
}