문제

https://school.programmers.co.kr/learn/courses/30/lessons/12945

나의 풀이

일반적인 피보나치 수 풀이

 class Solution {
    public int solution(int n) {

        List<Integer> f = new ArrayList<>();

        f.add(0);
        f.add(1);

        for (int i = 2; i < n+1; i++) {
            f.add(f.get(i-2) + f.get(i-1));
        }

        return f.get(n);
    }
}

이번 문제 피보나치 수 % 1234567

class Solution {
    public int solution(int n) {

        ArrayList<Integer> f = new ArrayList<>();

        f.add(0);
        f.add(1);
        f.add(1);

        for (int i = 3; i < n+1; i++) {
            f.add(f.get(i-2) % 1234567 + f.get(i-1) % 1234567);
        }

        return f.get(n) % 1234567;
    }
}

• 위의 일반적인 문제와 같이 단순하게 피보나치 수를 구한 뒤 % 1234567로 return 값만 반환하려 했다.
• 수가 커져서인지 테스트케이스는 오답처리 되어 위의 풀이처럼 구현하였다.
  
  
  
  

해결방안

- 어차피 1234567로 나눠도 그 이하 수는 그대로 나올텐데 왜 나눠주는지 궁금했다.
- 항상 쉬운 문제만 풀다보니 조건을 자세히 보지않아 java를 다룰 때에는 int형의 범위에 주의해야 한다는 점을 간과했다..

- 문제에서 `n은 2 이상 100,000 이하인 자연수` 라고 했다.
- int : -2^31 ~ 2^31-1 (-2,147,483,648 ~ 2,147,483,647)
- n = 44인 피보나치 수는 2,971,215,073로 int 자료형의 범위를 초과한다.
  -> 그렇기 때문에 피보나치 수를 구한 뒤에는 이미 범위 초과
  -> long 타입은 -9223372036854775808 ~ 9223372036854775807
  -> 100000 번째의 피보나치 수는 이 범위도 훨씬 초과(long으로 변경해도 x)
  
- (A+B)/C = (A/C) + (B/C) 기본적인 분배법칙을 활용하여 피보나치 수를 구해야 함

• 문제를 풀어서 정답을 찾는 것보다 조건을 정확하게 인지하고 나름의 단계를 설정하는 과정이 중요한데 마음이 급한 것 같다.
• 정확하고 알기쉽게 설명해 주신 분이 있어서 너무 좋았다. 나도 누군가에게 도움되는 날이 오기를

12945 피보나치 수 오답 이유