🔎 이렇게 푸셨나요?

% 1234567를 딱 한 번만 하셨나요?
오버플로우가 난 게 아닌가 의심돼요!

n이 매우 큰 경우 n번째 피보나치 수는 언어가 표현할 수 있는 자료형의 범위를 넘어가, 오버플로우가 납니다.

예를 들어

모든 단계에서 % 연산을 사용하여, 모든 연산에서 오버플로우가 일어나지 않게 만들어 주세요.

🔖TIP [나머지 연산의 성질]

나머지 연산은 다음과 같은 특징을 갖고 있습니다

(a + b) % m = ((a % m) + (b % m)) % m

이를 문제에 적용하면 다음과 같습니다

F(n) % m 
= (F(n-1) + F(n-2)) % m
= (F(n-1) % m + F(n-2) % m) % m

참고)

나머지 연산의 성질 - 피보나치