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

 

 

문제. 피보나치 수는 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+1 길이의 배열(pi)을 선언하여, pi[i-1] + pi[i-2] 한 값이 pi[i]에 저장한다.

마지막 pi[n]을 1234567로 나눈 나머지 값을 구한다.

 

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

        for(int i = 2; i < n+1; i++){
            pi[i] = pi[i-1] + pi[i-2];
        }

        return pi[n]%1234567;
    }
}

 

이렇게 정답을 제출해보니, 절반을 맞고 절반은 틀렸다고한다.

이유는 자연수 n이 100,000를 넘어가면 long의 범위를 오버플로우하게된다. 따라서, 합하여 값을 저장하기전에 1234567로 나눈 나머지값을 저장해야한다.

 

다른사람들이 제출한 정답을 보고 내 나름의 방식으로 재해석해보았다.

 

class Solution {
    public long solution(int n) {
        long pi0 = 0;
        long pi1 = 1;
        long pi2 = 1;

        for(int i = 2; i < n+1; i++){
            pi2 = (pi0 + pi1)%1234567;
            pi0 = pi1;
            pi1 = pi2;
        }

        return pi2;
    }
}

// 입력값
10

// 결과
55

 

 

 

링크.

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