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

문제

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

코딩테스트 연습 - 피보나치 수

풀이

피보나치 수를 구하는 문제이다.

일반적으로 피보나치 수는 재귀함수를 이용해서 푼다.

하지만 이번 문제에서는 재귀함수로 문제를 풀 경우 시간초과가 난다.

따라서 동적계획법을 이용해서 구한 값을 버리지 않고 저장하여 재활용하는 방법을 사용했다.

주의할 점

결과 값이 매우 큰 경우를 대비해서 마지막 결과값의 나머지를 구하는 문제들이 자주 출제된다. 

단순하게 마지막 결과 값에 모듈러 연산을 하면 되겠지 생각 할수도 있지만 과정속에서 이미 값이 커져 오버플로우가 발생할 수 있는 위험성이 있다. 따라서 모듈러 연산의 분배 법칙을 적용하여 연산 도중에 모듈서 연산을 적용해야한다.

 

(A+B)%C = (A%C + B%C)%C (모듈러 연산의 덧셈에 대한 분배법칙)

 

1234567으로 나머지 연산을 하게 되므로 결과값은 1234567보다 작아야 한다. 따라서 int형을 사용해도 된다.

 

코드

package 프로그래머스.레벨2.피보나치수.첫풀이;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;
/*
* 첫 번째 풀이에서 재귀함수를 이용해서 문제를 풀었다. 하지만 7번째 케이스부터 시간초과가 됐다.
* 그래서 두 번재 풀이로 동적계획법으로 풀었다. 동적계획법은 구한 값을 저장해 다음에 또 구할 때 사용하는 방법이다.
* */
public class Solution {

    static int[] dp;
    public int solution(int n) {
        dp = new int[100_001];

        return fibo(n)%1234567;
    }

    static int fibo(int n) {

        if (dp[n] > 0)  // n번째 피보나치를 구한 적이 있으면 값이 0이 아니다.
            return dp[n];

        if (n == 0) // 0번째 피보나치
            return dp[0] = 0;
        else if(n == 1) // 1번째 피보나치
            return dp[1] = 1;
        else    // 2번째 이상
            return dp[n] = fibo(n-2)%1234567 + fibo(n-1)%1234567;
    }

    @Test
    void test() {
        assertEquals(2, solution(3));
        assertEquals(5, solution(5));
    }
}