Skip to main content

[Java] 12945 피보나치 수

1. 문제

피보나치 수

2. 접근방법

피보나치수

피보나치 수는 수학에서 아주 유명한 수열이다.

가장 기본적인 정의는 아래와 같다

  • 첫 번째 수는 0
  • 두 번째 수는 1
  • 세 번째 수부터는 앞의 두 수를 더한 값

즉,

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

이런 식으로 계속 이어진다.

  • 0 + 1 = 1
  • 1 + 1 = 2
  • 1 + 2 = 3
  • 2 + 3 = 5
  • 3 + 5 = 8
    ... 이런 규칙이다.

3. 정답코드

class Solution {
    public int solution(int n) {
        // n 번째 피보나치수 % 1234567
        
        int MOD = 1234567;
        int a = 0, b = 1; // F(0), F(1)
        
        for (int i = 2; i <= n; i++) {
            int sum = (a + b) % MOD;
            a = b;
            b = sum;
        }
        
        return n == 0 ? a : b;
    }
}
  1. MOD 변수에 나머지 담기
  2. 피보나치 수 a, b 선언하고 0, 1로 초기화
  3. for문 순회하며 n까지 a + b의 합을 구하고, MOD로 나눈다.
    b는 a가 되고, sum이 b가 된다. 이것을 n까지 반복한다.
  4. n이 0이면 a를 리턴하고 아니면 b를 리턴한다.

어려웠던 점

  1. return 할 때 n이 0일때는 0리턴하는 처리해야 함. 그 외에는 다른 값 리턴함
  2. 오버플로우 처리
sum = (a + b) % MOD;
  • 미리 MOD로 나눈 값을 SUM으로 간주한다.
  • 이렇게 하는 이유는 피보나치 수가 엄청나게 커지기 때문이다.

오버플로우와 모듈러 연산

피보나치 수는 금방 폭발적으로 커진다.

  • F(10) = 55 → 작음
  • F(50) ≈ 12,586,269,025 → 벌써 100억이 넘어감
  • F(100) ≈ 3,542,248,481,792,703,274 → 19자리 수가 됨
  • 즉, 그냥 a+ b로 계산하면 int, long 범위를 금방 벗어나서 오버플로우가 난다.

문제 조건이 "n번째 피보나치 수 % 1234567" 이기때문에 정확한 수를 다 구할 필요는 없다.
나머지만 구하면 된다. 그래서 매번 계산할 때마다 미리 %MOD를 해주면 숫자가 커지지 않고 안전하게 나머지를 유지할 수 있다.
이것이 가능한 이유에 대해서 설명한다.

sum에 a + b를 나눈 값을 누적해서 나머지를 계속 더해도 결과가 같은 이유는 모듈러 연산 성질 때문이다.
모듈러 연산에는 이런 규칙이 있다.

(A mod M+B mod M) mod M=(A + B) mod M

원래 큰 수 A,B를 다 더한 뒤에 MOD를 취한 값과
각각을 미리 MOD로 줄여 놓고 더한 뒤 MOD를 취한 값이 항상 같다.

MOD = 10이라고 해보자.

  • 원래 값:
    • 123+789=912123 + 789 = 912123+789=912
    • 912 % 10 = 2
  • 미리 나머지 취한 값:
    • 123 % 10 = 3
    • 789 % 10 = 9
    • (3 + 9) % 10 = 12 % 10 = 2


Back to top