Study with book/Algorithms

[백준]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;
}

'Study with book > Algorithms' 카테고리의 다른 글

[백준]트리  (2) 2017.01.02
[백준]힙 정렬  (0) 2016.12.30
[백준]2xn 타일링  (0) 2016.12.23
[백준]순열 사이클  (0) 2016.12.22
[백준]DFS와 BFS3  (0) 2016.12.22