[프로그래머스(programmers)] (Lv2) 피보나치 수

알고리즘 문제 풀이 / 프로그래머스 (programmers)  - 피보나치 수

 

 

문제 링크

 

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

 

 

문제 풀이

 

BigInteger 를 사용하는것이 핵심이다.

 

 

피보나치 수 를 구현하는 것은 문제 설명대로 풀면 되는거라 중간에 걸릴 것 없이 너무 쉽게 풀었다. 그래서 이게 Lv2라는 것이 의심될 정도로 금방 풀었는데, 테스트케이스 중간쯤 부터 오류가 났다. 왜 오류일까 생각해보니 int 의 한계란 생각이 들었다. 그래서 long 으로 다 변환을 해줬는데 그럼에도 오류가 났다. 그래서 System.out 으로 풀이 과정을 찍어보았는데 고작 n = 888 이기만 해도 long 범위를 한참 초과해서 음수값으로 바뀌는 현상이 일어났다. 문제 조건에서 n 은 100000 이하 자연수이기 때문에 훨씬 더 초과하는 수가 많다는 말이다. 그래서 구글에 long 보다 큰 값 찾아보니 무한으로 생각하는 BigInteger 라는 것이 있었다. 이 문제 덕분에 새로운 것을 배웠다.

 

public static int solution(int n) {
    BigInteger num_re = BigInteger.ZERO;
    BigInteger num2 = BigInteger.ZERO;
    BigInteger num1 = BigInteger.ONE;
    BigInteger mod = new BigInteger("1234567");
    int count = 1;
        
    while(count < n) {
       	num_re = num1.add(num2);
       	num2 = num1;
       	num1 = num_re;
      	count++;
    }
        
    int answer = (num_re.mod(mod)).intValue();
    return answer;
}