프로그래머스, C++) Lv 2. 멀리뛰기

문제

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

프로그래머스

 

 

• 노트로 직접 해본 결과, 피보나치 수열과 동일했다. 
• %1234567을 나중에 해줬을 때, 테스트 케이스 8? 9번부터 실패가 뜸.
• 원인 분석 결과 수가 커져서 +연산이 제대로 안될 수 있기 때문
• 그렇기 때문에 연산량이 조금 늘어나지만 미미하기에 모든 수 계산에 %1234567을 적용

#include <iostream>
#include <string>
#include <vector>

// 피보나치 수열

using namespace std;

long long solution(int n) {
    vector<long long> nums(n+1);
    nums[1] = 1;
    nums[2] = 2;

    for(int i = 3; i <= n; ++i)
        nums[i] = (nums[i-1] + nums[i-2]) % 1234567; // 모듈러는 미리 적용

    return nums[n];
}