#include <string>
#include <vector>
using namespace std;
int solution(int n)
{
int ans = 0;
int F[100001];
F[0] = 0; F[1] = 1;
for (int i = 2; i <= n; i++)
F[i] = (F[i - 1] + F[i - 2]) % 1234567;
ans = F[n];
return ans;
}일반적인 Recursive 방식으로 풀게 된다면 시간초과가 나게 된다.
이 뜻은 DP로 memoization해야한다는 뜻이다. Recursize 방식으로 풀게 된다면 값이 커졌을 때 계산한 부분에 대해서 또 계산을 하게 되므로 시간 손실이 많이 일어난다. 그래서 F의 값을 저장해두고, 그 값이 필요할 때 꺼내서 사용하는 방식을 이용하면 된다.
for문에서 i - 1, i - 2부터 계산되므로 F[ 0 ]과 F[ 1 ]에 0과 1 이라는 초기값을 넣어준다. 그 후 2부터 시작하여 차례차례 계산해나가면 값을 구할 수 있다.
·ᴗ·