# \[99클럽 코테 스터디 21일차 TIL]  프로그래머스 - 피보나치 수

## \[level 2] 피보나치 수 - 12945

[문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/12945)

#### 문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

* F(2) = F(0) + F(1) = 0 + 1 = 1
* F(3) = F(1) + F(2) = 1 + 1 = 2
* F(4) = F(2) + F(3) = 1 + 2 = 3
* F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

**제한 사항**

* n은 2 이상 100,000 이하인 자연수입니다.

**입출력 예**

| n | return |
| - | ------ |
| 3 | 2      |
| 5 | 5      |

**입출력 예 설명**

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

***

## 풀이 코드

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

* Time: 3.11 ms
* Memory: 74.4 MB

풀이 코드 자체는 간단하다. `n` 번째 피보나치 수를 구해서 `1234567` 로 나눈 나머지를 반환하면 되기 때문에 배열의 크기를 `n + 1` 로 선언해야 `n` 번째 피보나치 수를 구할 수 있다. 이렇게 생각해서 `n` 번째 피보나치 수를 가져와서 `1234567` 로 나눈 나머지를 반환하면 절반만 정답이 된다.

왜냐하면 46번째 피보나치 수가 `1,836,311,903` (18억 3631만 1903) 이기 때문에 47번째부터는 정수형의 범위를 가뿐히 넘어간다. 심지어 `n` 은 10만 이하의 수이기 때문에 `long` 자료형도 금방 넘어가게 된다.

이를 해결하기 위해 `1234567` 로 먼저 나눠서 배열에 담으면 풀이에 성공한다. 그런데 이 과정에서 이해가 안되는 부분이 있었다. 범위를 넘어가는 문제를 해결하기 위해서 처음엔 아래와 같이 풀었다.

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

이렇게 풀면 틀린 풀이가 된다. 왜냐하면 피보나치 수 29번째와 30번째는 아래와 같다.

* 29번째 피보나치 수 : 514229
* 30번째 피보나치 수 : 832040

이제 31번째 피보나치 수에 `1234567` 을 나눈 값을 정답 풀이 코드와 틀린 풀이 코드로 구해보자.

* 정답 풀이 : (514229 + 832040) % 1234567 -> 1346269 % 1234567 = **111702**
* 틀린 풀이 : 514229 % 1234567 + 832040 % 1234567 -> 514229 + 832040 = **1346269**

위처럼 `n-1 + n-2` 의 값이 `1234567` 을 넘어가는 순간에 두 풀이에 차이가 생긴다. 그래서 이 다음으로 푼 풀이는 반환할 때 한번 더 `1234567` 을 나누는 방법이었다.

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

앞서 정답 풀이와 틀린 풀이를 비교한 연산 과정을 따라가면 위 풀이가 왜 정답인지는 쉽게 유추가 가능하다. 따라서 아래와 같은 결론이 도출된다.

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

찾아보니 위 법칙은 모듈로 연산 분배 법칙 중 덧셈에 대한 법칙이다. 증명은 아래와 같다.

### 모듈로 연산 분배 법칙 - 덧셈 증명

* 좌변 - (a + b) % m
  * (a + b) % m 는 a + b를 m 로 나눈 나머지이다.
  * a % m 는 a - m \* k1, b % m = b - m \* k2 로 표현할 수 있다.
  * a + b - m \* (k1 + k2) = a + b - m \* k3 이므로 (a + b) % m = a % m + b % m 은 성립한다.
  * 합동식으로 표현하면 a + b = a + b (mod m) 이다. 즉, a % m + b % m = (a + b) % m 이다.

{% hint style="info" %}
**합동식이란?**

고정된 양의 정수 m(!= 1)에 대해 두 정수 a, b가 m | (a - b) 를 만족할 때, a 와 b 는 m 을 법으로한 합동 또는 합동식이라고 부르고 기호로는 `a = b (mod m)` 으로 표현한다.

( | 의 의미는 (a - b) 는 m 으로 나누어 떨어진다는 의미로 a - b 가 m 으로 나누어 떨어진다면, a = b (mod m) 으로 표현하겠다는 것이다. 다르게 말하면 a 와 b 는 m 에 의하여 나눠 졌을 때의 나머지가 동일하다는 것을 의미한다. )
{% endhint %}

* 우변 - (a % m + b % m) % m
  * 앞서 좌변의 증명에 따라 a + b = a + b (mod m) 이므로, a % m + b % m = (a + b) % m 은 성립한다.
  * 따라서 (a % m + b % m) % m = ((a + b) % m) % m 이고, (a + b) % m 을 m 으로 나눈 나머지는 (a + b) 를 m 으로 나눈 나머지와 동일하다.
  * 따라서 (a + b) % m = a + b (mod m) 이다.

따라서 (a + b) % m = a % m + b % m, (a % m + b % m) % m = ((a + b) % m) %m = (a + b) % m 이므로 (a + b) % m = (a % m + b % m) % m 은 성립한다.

모듈로 연산 분배 법칙은 덧셈 뿐만 아니라 곱셈과 뺄셈에도 성립된다.

> 곱셈 - (a \* b) % m = ((a % m) \* (b % m)) % m
>
> 뺄셈 - (a -b) % m = ((a % m) - (b % m) + m) % m # 음수 방지를 위해 m 을 더해준다.

***

## 돌아보기

수학 공부를 차근 차근 다시 하고 싶단 생각이 든다. 언제 한번 로드맵을 찾아봐야겠다. 중학 수학부터 배우면 될까?

### 다음에는

* 자료형의 범위를 항상 유의하기
* 결과 값 출력하면서 디버깅하기

***

\#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://devlee.gitbook.io/docs/study/99/99-21-til.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.