프로그래머스 lv2 멀리뛰기 자바(Java) 동적계획법/ 피보나치수열

필자는 위의 유형과 같은 문제를 풀다 해결법이 안나오면 스케치를 해봅니다.

그러다 우연히 발견한것은 N에 대한 정답의 값이

n-1과 n-2 의 합과 같은 패턴

이것은 피보나치 수열입니다.

대부분의 알고리즘 문제에서 피보나치수열은 시간복잡도를 많이 소요하기 때문에 통과하기 어렵습니다.

자세한 설명과 이유는

https://eccsck.tistory.com/51에 있습니다.

역시나, 결과는 시간 초과입니다.

 

이번에는 배열을 통해 이전값들을 저장하고 다시 불러오는 동적 계획법을 이용해서 풀이해보겠습니다.

n의 크기만큼 값을 구하여 각각의 값을 저장하게 됩니다.

그렇게 되면 이전의 값을 구하기 위해 다시 계산하지 않기때문에 시간복잡도를 줄일수있습니다

확실히 시간복잡도가 개선 되어서 통과하게 되었습니다

public class LongJump {
    public long solution(int n) {
        long []cache =new long[n+1];
        cache[0]=1;
        cache[1]=2;
        for (int i=2; i<n;i++){
            cache[i]=(cache[i-1]+cache[i-2])%1234567;
        }
        return cache[n-1];
    }
}

 정답코드입니다.

혹시 풀이내용이 이해안가시면 댓글로 남겨주세요