[프로그래머스] 2단계 - 피보나치 수

문제 설명

n번째 피보나치 수를 1234567로 나눈 나머지를 return

https://school.programmers.co.kr/learn/courses/30/lessons/12945?language=cpp

프로그래머스

 

문제 풀이법

해당 문제는 n이 47일 때부터 int 자료형의 범위를 벗어나 버린다

따라서 자료형의 범위를 넘지 않게 vector에 피보나치 수열을 저장해야한다

문제에서 피보나치 수를 1234567로 나눈 나머지를 return 하라 했으니, 여기서 힌트를 얻어서 값을 저장해주면 된다

 

피보나치 수열에서 F(0) = 0, F(1) = 1 일때, F(n) = F(n - 1) + F(n - 2)이므로 우선 0번째와 1번째를 초기화 해두고 나머지는 n까지 for문을 통해 피보나치 수열을 구해준다

이때 저장할 때 F(n) = {(F(n - 1) % 1234567) + (F(n-2) % 1234567)} % 1234567로 저장한다

 

만일,  F(n) = (F(n - 1) % 1234567) + (F(n-2) % 1234567)로만 저장한다면 이 또한 int 값을 넘어버리니 꼭 마지막에 1234567를 나눈 후에 저장해줘야 한다 

 

소스 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<long> fibonacci;
    
    fibonacci.push_back(0);
    fibonacci.push_back(1);
    
    for (int i = 2; i <= n; i++) {
        int tmp = fibonacci[i - 1] % 1234567 + fibonacci[i - 2] % 1234567;
        fibonacci.push_back(tmp % 1234567);
    }
    
    answer = fibonacci[n];
    
    return answer;
}