[프로그래머스] 멀리 뛰기 (Java)

프로그래머스

1 또는 2를 더하여 주어진 n까지 도달할 수 있는 경우의 수를 계산한 후 1234567로 나눈 나머지를 구하는 문제이다.

 

- DFS를 재귀로 구현하여 사용했는데 시간초과가 발생함

- 구현하고보니 피보나치수열임을 발견, 배열로 변경하여 문제 해결

 

Note

- for문 내부에서 덧셈 연산 시 1234567로 바로 나누어 나머지를 배열에 저장했다. 덧셈 결과만 먼저 저장하는 경우 오버플로우 발생으로 테스트 케이스 7번부터 끝까지 실패한다.

class Solution {
    public long solution(int n) {
        long[] arr = new long[n];
        
        if(n == 1){
            return 1;
        }else if(n == 2){
            return 2;
        }
        
        arr[0] = 1;
        arr[1] = 2;

        for(int i = 2; i < arr.length; i++){
            arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567;        
        }   

        return arr[arr.length - 1];
    }
}