[Coding Test] 프로그래머스 2단계 - 멀리 뛰기

📚 문제

 

✏️ 메모 

 

n = 1 일 때, 1 >> 1
n = 2 일 때, (1, 1), (2) >> 2
n = 3 일 때, (1, 1, 1), (2, 1), (1, 2) >> 3
n = 4 일 때, (1, 1, 1, 1), (2, 1, 1), (1, 2, 1), (1, 1, 2), (2, 2) >> 5
n = 5 일 때, (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (2, 1, 1, 1), (1, 2, 2), (2, 1, 2), (2, 2, 1) >> 8 
1 2 3 5 8 .... 피보나치 수열 

Java 피보나치(Fibonacci) 수열 제대로 풀기

✏️ 메모 

왜 1234567 을 나누는가? 

- 모든 연산이 그대로 진행되고, 결과가 큰 값으로 커질 수 있음. 입력값이 커지면 오버프로우 위험에 노출됨. 

- 지수적으로 커지는 피보나치 수열이 1234567을 넘지 않도록 제한 함. 

- 다른 숫자는 안되는가? 됨. 오버플로우를 방지할 수 있을만큼 크지만 계산 효율성이 있을만큼 작은 소수 일 뿐. 

피보나치 문제 풀 때 왜 1234567로 나눈 나머지를 사용해야 하는가

 

🔎 문제해결

class Solution {
    public long solution(int n) {
        long answer = 0;
        
        long num1 = 1;
        long num2 = 1;
        
        long result = 0;
        
        if (n == 1 ) return 1;
        
        for (int i = 2; i <= n; i ++) {
            // 피보나치 수열 
            result = (num1 + num2) % 1234567;
            num1 = num2;
            num2 = result;
        }
        
        
        return result;
    }
}