[백준]2xn 타일링

백준저지

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

• 다이나믹 프로그래밍(=동적 계획법, DP)으로 분류되는 문제이다.

• DP는 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 방법이다.

• 위 문제를 필자는 노가다(?)로 작업을 해보았다. 그리고 다음과 같은 규칙을 얻을 수 있었는데

• 바로 피보나치 수열의 점화식을 얻을 수 있었다.

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

• 아래는 구현 코드인데 쉽게 구할 수 있었다.

#include <iostream>

using namespace std;

int main(void) {

	int result[1001] = { 0, };
	int num;

	cin >> num;
	result[1] = 1;
	result[2] = 2;

	for (int i = 3; i <= num; i++) {
		result[i] = (result[i - 1] + result[i - 2])%10007;
	}
	cout << result[num];
	return 0;
}