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

- 문제

- 풀이

// 최종풀이
class Solution {
    public int solution(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        int[] arr = new int[n + 1];

        for (int i = 0; i < arr.length; i++) {
            if (i == 0) arr[i] = 0;
            else if (i == 1) arr[i] = 1;
            else {
                int aTmp = arr[i - 1] % 1234567;
                int bTmp = arr[i - 2] % 1234567;
                arr[i] = (aTmp + bTmp) % 1234567;
            }
        }


        return (arr[arr.length - 1] % 1234567);
    }
}

- 정리

이번 문제는 배우고 알아가야할 것들이 많아 내가 했던 풀이를 소개하고, 비교해보는 식으로 하겠다.

- 내가 틀린 1차 풀이

class Solution {
    public int solution(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        int[] arr = new int[n + 1];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i-2] + arr[-1];
        }


        return (arr[arr.length - 1] % 1234567);
    }
}

이것이 내가 계속 헤맸던 풀이다. 단순하게 생각했을 땐 이게 당연히 맞다고 생각했다. 그 이유는 바로 내가 입력값 n을 계속해서 작은 값(3, 5, 8)등을 줬기 때문이다. 그러니까 당연히 int의 범위, long의 범위를 벗어날 것이라고 생각을 못했다. 그러나 반복되는 7~18번 케이스의 실패로 다시한번 문제를 살폈고, 계속해서 탐구하다보니 숫자가 크게 늘어날 것이라고 생각했다. 그러고 난 후의 2차 풀이.

- 내가 틀린 2차 풀이

class Solution {
    public int solution(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        long[] arr = new long[n + 1];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i-2] + arr[-1];
        }


        return (int) (arr[arr.length - 1] % 1234567);
    }
}

정말 단순하게 2차코드를 완성했다. int의 범위를 조금 벗어날 것이라 예상하고 이보다 더 큰 범위인 long을 사용하여 풀이하였다. 그러나 여전히 똑같은 케이스들에서 틀렸다. 한참된 고민 끝에 힌트를 봐야겠다하고 힌트를 확인했다.

- 확인한 힌트들

이 힌트들을 보고 두 가지를 느꼈다. 하나는 수학적 정의를 몰랐고, 하나는 숫자의 범위이다.

F(n) % m
= (F(n-1) + F(n-2)) % m
= (F(n-1) % m + F(n-2) % m ) m

이 코드를 보고

아 나는 수학을 아직 쥐똥만큼도 모르구나. 모르니까 적용할 줄 몰랐구나

생각했다. 또한 int형, long형 범위를 아주 가볍게 인식하고 있어 어디까진지 대충 때려맞추는 식으로 풀었던 것 같다. 이 코드를 보고 바로 깨우치고 적용한 나의 마지막 풀이를 보자.

- 최종답안.

class Solution {
    public int solution(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        int[] arr = new int[n + 1];

        for (int i = 0; i < arr.length; i++) {
            if (i == 0) arr[i] = 0;
            else if (i == 1) arr[i] = 1;
            else {
                int aTmp = arr[i - 1] % 1234567;
                int bTmp = arr[i - 2] % 1234567;
                arr[i] = (aTmp + bTmp) % 1234567;
            }
        }


        return (arr[arr.length - 1] % 1234567);
    }
}

바로 arr[i]에 넣는 것이 아닌 각각 나누고, 더해서 나눈 값을 넣어 수의 크기를 최대한 낮추는게 핵심인 것같다. 이에 관련된 모듈러 연산 법칙을 공부해야겠다.

[링크] : 도움 준 블로그
[링크] : 개인저장소