[프로그래머스 JAVA] 피보나치 수

간단한 문제인데 long 자리수를 설마 넘어가나? 싶어서 오래걸렸다.

 

1. 문제 요약

2 이상의 n이 입력되었을 때,  n번째 피보나치 수를 1234567으로 나눈 나머지를 구하는 문제이다.

n은 100,000 이하의 자연수이다.

 

2. 내가 막혔던 지점

n 이 재귀로 풀기엔 크기 때문에 반복문으로 접근하였고 Integer가 감당하지 못할꺼같아서 처음부터 long으로 풀었다.

 

제출했을때 중반부터 끝까지 쭉 틀리는것을 보고 이거는 오버플로우가 나는거같았지만 long 이상의 어떤 무언가를 표현하기에는 문자열로 해야하는데 그러면 시간이 너무 오래걸릴꺼같았다.

 

즉, long이상의 오버플로우를 해결하지 못했다.

 

3. 핵심아이디어

 

100,000번째 피보나치 수는 자릿수가 20,000을 넘어가며, 이는 64비트 정수(ex. long) 범위를 넘어 오버플로우가 발생한다.

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

 

나머지 연산의 성질을 이용했는데

 

(a + b)  % m = ((a % m) + (b % m)) % m 이다.

 

4. 실수 포인트새로운 방법을 알게되었다.

 

5. 코드

class Solution {
    public int solution(int n) {
        int[] F = new int[n + 1];
        F[1] = 1;
        for(int i = 2; i <= n; i++){
            F[i] = (F[i - 1] % 1234567 + F[i - 2] % 1234567) % 1234567;
        }
        
        return F[n] % 1234567;
    }
}

 

 

여기 까지가 정석이고 아직도 왜 이 나머지 연산의 성질이나 가 이해가 안된다면

어떤 수 a를 m으로 나누면

 

a = m * k + r (r = a % m)

이렇게 쓸 수 있다.

그럼 두 수 a, b를 더하면:

 

a + b = (m*k1 + r1) + (m*k2 + r2) = m*(k1 + k2) + (r1 + r2)

여기서 중요한 건
m의 배수 부분은 나머지에 전혀 영향이 없다는 것이다.

 

따라서

 

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

 

즉,

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

이 되는것이다.

 

이전값이 왜 영향을 안미치냐면 F[i-3]을 % m로 줄여서 저장해도

 

그 값이 미래에 더해지고 더해져도 최종적으로 우리가 관심 있는 건 “mod m”

 

그리고 덧셈은 mod에서 닫혀 있어서 미래의 mod 결과는 1도 안 변함