[BOJ/C++] 11726 2×n 타일링 : DP

문제

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

풀이

규칙을 찾으려고 경우의 수를 생각해봤는데 1-> 2-> 3-> 5-> 8 이런 식이라서 n = (n-1) + (n-2)라는 것을 발견했는데 왜 그렇게 되는지는 모르고 눈치껏 풀었다 ,,

규칙

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int N;
	vector<int> v;

	cin >> N;
	v.push_back(0); //0을 나타내는 경우의 수
	v.push_back(1); //1을 나타내는 경우의 수
	v.push_back(2); //2를 나타내는 경우의 수

	for (int i = 3; i <= N; i++) {
		int tmp;

		tmp = (v[i - 1] + v[i - 2]) % 10007;
		v.push_back(tmp);
	}

	cout << v[N] << endl;

	return 0;
}