프로그래머스 - 피보나치 수 - C++

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

프로그래머스

 

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    int a=0;
    int b=1;
    
    for(int i=2;i<=n;i++)
    {
        answer=(a%=1234567)+(b%=1234567);
        answer%=1234567;
        a=b;
        b=answer;
    }
    
    return answer;
}

 

피보나치 수를 구하는 문제인데, n 번째 수에서 1234567를 나눈 나머지를 리턴해야한다.

n이 최대 십만까지라서 인트형의 범위를 넘어갈지도 몰라 

f(n) = f(n-1) + f(n-2) 에서 f(n-1)과 f(n-2)에 각각 먼저 나머지연산을 하고 더하기 계산 후 다시 나머지 연산을 했다.