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

문제 설명

피보나치 수는 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, ... 와 같이 이어집니다.

 

 

첫번째 풀이는 재귀를 이용하고자 했다.

근데 테스트케이스에서 시간초과...

 

원인을 찾아보니 재귀가 어느정도 이상 들어가면 진행이 되지 않는다고 한다..

 

public class Quiz33_시간초과 {
    public static void main(String[] args) {
        int n = 3;
        int answer = 0;

        answer = fiboReturn(n);

        System.out.println(answer);
    }

    public static int fiboReturn(int n) {
        if (n < 2) {
            return n% 1234567;
        } else {
            return (fiboReturn((n - 2)) + fiboReturn(n - 1)) % 1234567;
        }


    }
}

일단 피보나치의 수를 구할 수 있는 공식을 문제에서도 알려주고 있고,

심지어 내가 메소드에도 써뒀는데 엄청나게 헤맸다..

 

 

여튼 답은,

class Solution {
    public int solution(int n) {
      int[] fibo = new int[n + 1];
        fibo[0] = 0;
        fibo[1] = 1;


        for (int i = 2; i < fibo.length; i++) {
            fibo[i] = (fibo[i - 2] + fibo[i - 1]) %1234567;

        }

       int answer = fibo[n];
    return answer ;
    }
}

먼저 배열을 이용했다. 위 코드에서는 주어진 n+1만큼의 길이를 만들고, 시작되는 값인 0,1번째 값들을 미리 지정해 두었다.

 

그리고 질문하기에 내가 막혔던 부분을 누군가 정말 정성스럽게 작성해 둔 글이 있었다.

https://school.programmers.co.kr/questions/36767

프로그래머스

 

피보나치 수 44만 해도 2,971,215,073로 int의 값을 훨씬 넘은 수라 표현이 안되는 것이다.

그래서 애초에 피보나치 수를 구하는 과정에서 1234567로 나눈 나머지 값을 반환하도록 했다.

 

그러니까 통과..!

 

아직 갈 길이 멀다..

문제도 뭔가 얼떨결에 풀고, 우왕좌왕 한다.