[Java/자바] 프로그래머스 Lv2 - 피보나치 수

문제 설명

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

---

Solution.java

이번 문제를 푸는데 DP 문제를 활용하였습니다.

이전 포스팅에 DP에 대한 설명으로 피보나치에 대해 설명한 글이 있는데 아래 포스팅을 참고하시면 코드 이해에 조금 도움되실 겁니다.

[알고리즘] 동적 프로그래밍 (DP) 란? feat.동적 계획법

 

public class 피보나치수 {
    public static void main(String[] args) {
        System.out.println(solution(5));
    }

    public static int solution(int n) {
        int[] answer = new int[n + 1];
        answer[0] = 0;
        answer[1] = 1;

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

        return answer[n];
    }
}

이 문제는 문제 설명을 "자세히"읽어 봐야하는데요, 문제를 보면

"n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요."라고 되어 있습니다.

만약 n번째 피보나치 수를 1234567로 나누지 않는 다면 테스트 케이스 7번부터 오류가 발생합니다.

 

그 이유는, 47번 째 피보나치 수는 2,971,215,073으로 int 정수형의 범위인 2,147,483,647을 넘어가 오버플로우가 발생하게 되기 때문입니다.

 

그래서 이 문제에서 n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수를 완성하라 한 것입니다.