백준 1904 풀이

dp 문제이며 n==5까지 해보면 금방 규칙을 찾을 수 있는 간단한 문제이다.

F(n) = F(n-1)+F(n-2)

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;

int t;
int n;
int m;
int arr[1000001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	
	arr[0] = 0;
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 3;

	for (int i = 4; i <= n; i++) {
		arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;
	}
	cout << arr[n] << '\n';
	return 0;
}