[프로그래머스/Lv.2] 피보나치 수

1. Input

1) 자연수 n

 

2. Output

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

2) F(0) = 0, F(1) = 1일 때 F(n) = F(n-1) + F(n-2)

 

3. Constraint

1) n은 2 이상 100,000 이하의 자연수

 

4. Example

Input: n=5 -> Output: 5

설명: 피보나치 수는 0, 1, 1, 2, 3, 5, ...이므로 5번째 수인 5를 1234567로 나누면 나머지는 5가 된다.

 

5. Code

1) 첫 코드(2022/??)

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

  - overflow 방지를 위해 (a+b)%n은 a%n + b%n과 같음을 이용