피보나치 수 - 12945

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 1;
	vector<int> v;

	v.push_back(0);
	v.push_back(1);

	if (n < 3)
        return answer;
    for (int i = 2; i <= n; i++)
		v.push_back((v[i-2] + v[i-1]) % 1234567);
	answer = v[n];
	return answer;
}

• 피보나치 수를 구하는 문제
• 피보나치는 0+1+1+2+3+5........ 이렇게 더해가는 규칙을 갖는다
• 이를 수식으로 표현하면 f(n) = f(n-1)+ f(n-2)이다
• 이를 사용해 수식을 구하기 위해 vector를 이용해 계산된 결과 값들을 계속 들고갈 것이다
• 예외처리로 n 이 2보다 크거나 같은 수부터 시작이고, n == 2일 땐 무조건 1이므로 예외처리를 하여 시간을 줄여준다
• 나머지 값들은 i = 2부터 n과 같을때 까지 vector에 저장된 수를 이용해 점화식을 구현한 값을 vector에 저장해주면 된다