[Programmers/C++] 피보나치 수

 

💣 무슨 짓을 해도 테스트케이스 절반이 통과가 안 된다!

 

정~말 무식하게 문제를 해결하려 했다.

 

뒤로 갈수록 피보나치 수가 어마어마하게 커져서 int형의 범위를 넘어간다는 건 디버깅을 통해 진즉에 알아챘지만..

이걸 long으로 바꿔보고 long long으로 바꿔보고 unsigned long long으로도 바꿔보고...  

 

결국 다 처참하게 실패하고 다시 int형 내에서 해결해 내야겠다는 생각을 먹으니... 결국 해결해 버렸다.

 

실패로 배운건 많지만... 으으아ㅏㄱ 그래도 진정이 안 돼!!

 

 

문제

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

 

❗ n의 범위가 생각보다 크다.

 

 

 

 

 

입출력 예시

입출력 예시

 

입출력 예시

 

 

 

---

 

풀이 

#include <vector>
using namespace std;

vector<int> fib;

int solution(int n) {
    for (int i = 0; i < n + 1; ++i) {
        if (i < 2) {
            fib.push_back(i);
        }
        else {
            fib.push_back((fib[i - 1] + fib[i - 2]) % 1234567);
        }
    }
    
    return fib[n];
}

• 피보나치 수를 저장할 때마다 1234567로 나눈 나머지 값을 저장해주는 게 핵심이다.
• (A + B) % C의 값은 ( ( A % C ) + ( B % C) ) % C와 같다는 모듈러 연산의 성질을 이용한 것이다.
  • 모듈러 연산의 자세한 내용은 아래 링크를 참고하자.

 

모듈러 산술 - 위키백과

모듈러 산술 - 위키백과, 우리 모두의 백과사전

 

 

---