피보나치 수

• 피보나치 수열을 만들기 위해 재귀보다 DP방식이 빠르다는 것을 알아야 한다
• 모듈러 연산 성질 을 통해 합을 줄이는 방법을 알고 있어야 한다.

/* 모듈러 연산 성질 */
(a + b) % c = ((a % c) + (b % c)) % c

코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    int before = 0;
    int after = 1;
    if(n == 1) return 1;
    for(int i=2;i<=n;i++) 
    {
        /* 모듈러 연산법칙 이용! */
        int sum =  ((before%1234567) + (after%1234567))%1234567;
        before = after;
        after = sum;
    }
    answer = after;
    return answer;
}

• 피보나치의 경우에 재귀는 비효율적이기 때문에 DP방식으로 점화식을 구해서 속도 향상!
• 또한 어떤 수로 나누라는 문제는 모듈러 연산 성질을 이용하라는 문제가 많음을 기억 !!