[algorythm] 백준 1904번 cpp

문제

일단 DP문제 답게 먼저 생각해보자

1일때

1

2일때

00
11

3일때

001
100
001

4일때

0000
0011
1100
1111

점화식은 arr[a - 1] + arr[a - 2]이다.

나는 재귀함수로 풀었다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> numArr(1000001);

long long int f(int a) {
	if (a == 1) return 1;
	if (a == 2) return 2;
	if (numArr[a] != 0) return numArr[a];
	else return numArr[a] = (f(a - 1) + f(a - 2)) % 15746;
}

int main() {
	int a;
	cin >> a;

	cout << f(a);
}