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

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

 

🖊️문제 설명

처음에는 피보나치 수를 계산할 때 많이 사용하는 재귀를 이용해서 문제를 풀었는데 테스트 결과 시간 초과가 계속 발생했다.

  public int solution(int n) {
    if(n<2 || n >100000){
      return 0;
    }
    return fib(n) % 1234567;
  }

  public int fib(int n){
    if(n <= 2){
      return 1;
    }
    return  (fib(n-1) + fib(n-2) ) % 1234567;
  }

 

어떻게 코드를 개선할 수 있을까 생각해보다 누적합을 이용하는 방법을 생각했다.

피보나치는 F(n) = F(n-1) + F(n-2) 의 공식을 갖고 있으니까, 배열을 이용해 합을 누적시키면서 arr[i-1] + arr[i-2] = arr[i]가 될 수 있도록 코드를 작성하였다.

 

배열 길이는 n은 2이상 100,000이하인 자연수라는 제한 사항이 있으니까 100,000+1 로 설정해서 문제를 풀어주었다.

 

🖊️코드

 public int solution(int n) {
    int fib[] = new int[100001];
    fib[0] = 0;
    fib[1] = 1;

    for (int i = 2; i <=n ; i++) {
      fib[i] = (fib[i-1]+fib[i-2])%1234567;
    }
    return fib[n];
  }

 

시간 복잡도 면에서 개선이 크게 된 것을 확인할 수 있었다!

 

 

fib[i] = (fib[i-1]+fib[i-2])%1234567;   이렇게 작성해준 이유는 

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

라는 문구가 문제 안에 적혀있었기 때문에 아예 배열에 값을 저장해주는 과정에 수를 1234567로 나눈 나머지를 넣어 주었다.