백준 1940 C++

#include <bits/stdc++.h>

using namespace std;

int n;	//<=1000000
int dp[1000010];

int go(int num)
{
	if (num == 1) return 1;
	if (num == 2) return 2;

	if (dp[num] != 0) return dp[num];

	int& result = dp[num];

	//이 식이 나오는 이유
	//n-1에 있는 수 제일 뒤에 1을 추가하는 경우의 수와 n-2에 00을 추가하는 경우의 수가 총 n의 경우의 수와 동일하다.
	return result = (go(num-1) + go(num-2)) % 15746;
}

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

	cin >> n;

	cout << go(n);
}

간단하게 생각할 수 있는 문제였다.