[백준] 11726번 2×n 타일링

11726번: 2×n 타일링

동적 계획법으로 풀었다.

규칙이 있다.

2 x n을 채우는 방법의 수 = 2 x (n - 1)을 채우는 방법의 수 + 2 x (n - 2)를 채우는 방법의 수이다.

int의 범위를 벗어날 수 있으니 애초에 저장할 때 10007로 나눈 나머지를 저장해주었다.

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int* arr = new int[n];
	arr[0] = 1;
	arr[1] = 2;
	for (int i = 2; i < n; i++) {
		arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
	}
	cout << arr[n - 1];
	return 0;
}