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

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

프로그래머스

Level 2. 피보나치 수 

 

접근 방식

 (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C 를 이용할 것

 

 

처음 코드

public class Study {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int n = 5;
		
		Study(n);
	}
	
	static int fibo(int n) {
		if(n<=1)
			return n;
		
		else {
			return fibo(n-1)+fibo(n-2);
		}
	}
	
	public static int Study(int n) {	
		return fibo(n)%1234567;
	}
}

처음엔 단순히 피보나치 함수를 만들어서 테스트 했다. 예제 역시 맞는 답이 나오길래 간단하군! 했는데, 채점을 했더니 7번부터 오답이라고 나왔다.

예전에 이렇게 int 자료형에 대해 오버플로우가 나오는 문제를 푼 적이 있었어서, 그때 했던 대로 long 형태로 변환해서 반환시켰더니 여전히 틀린 답이었다. 인터넷에 검색해보기로 했다..

 

최종 코드

public static int Study(int n) {	
		int answer = 0;
		
		int[] fibo = new int[n+1];
		fibo[0] = 0; fibo[1] = 1;
		
		for(int i=2; i<=n; i++) {
			fibo[i] = (fibo[i-1]+fibo[n-2])%1234567;
		}
		
		return fibo[n];
	}

 

고찰

문제 풀이를 찾아보다가 엄청난 깨달음을 주는 글을 발견했다.

"44번째 피보나치 수만 가도 2,971,215,073로 int 범위를 넘어버립니다. " 해당 문제는 int형으로 반환되는 문제로, 결과값이 int가 나와야 하는데 44번재 피보나치 수만 해도 int 범위를 넘어선다는 것이다. 따라서, 내가 작성한 첫 코드와 같은 방법으로는 int 오버플로우가 발생하여 제대로 된 값이 나올 수 없다. 

자료형의 제약이 있는 자바의 성질을 고려하여,  (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C 을 고려하여 코드를 작성하여야 정답을 확인할 수 있었다.