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

문제

---

피보나치 수는 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을 완성해 주세요.

 

-  출력 예시  -

정답 코드

---

<  내 정답 코드  >

class Solution {
    public int solution(int n) {
        long answer = 0L;
        long num = 0L;
        long preNum = 1L;
        long nextNum = 1L;
        int a = 1234567;

        for (int i = 2; i < n; i++) {
            num = (preNum % a) + (nextNum % a);
            preNum = nextNum;
            nextNum = num;
        }

        return (int) (num % 1234567);
    }
}

 

<  타인 답변 코드  >

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

    	for(int i = 2 ; i <= num; i++){
             dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567L;
    	}

        return dp[num];
    }
}

이것을 주의하자!

---

-  피보나치 수열을 구하는 방법은 for 문과 배열이 있다. for 문으로 구현할 경우, 맨 앞 부분의 특수한 경우(0, 1, 1)을 제외하곤 이전 원소를 다음 원소로 위치를 바꿔주면 된다.

 

-  배열은 Long 타입 배열을 만든 다음, 인덱스 0,  1 에는 미리 0 과 1을 대입해두고, 다음 원소에 값을 계산해서 넣으면 된다. 처음 배열을 만들 때 크기는 n + 1 개가 된다.

 

-  피보나치 수는 조금만 지나도 수의 크기가 엄청 커지기 때문에 long 형으로 해도 역부족이다. 따라서 ' % 1234567 '을 해주는데, 맨 마지막뿐만 아니라 각각의 경우의 수마다 % 을 해줘서 수 길이를 조절해줘야 한다.