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

프로그래머스 - 멀리 뛰기

class Solution {
   
    public long solution(int n) {
        // 1. n번째 칸 까지 가는 경우 : n-1 칸에서 1칸 점프 or n-2칸에서 2칸 점프
        // arr[n] = arr[n-2] + arr[n-1];
        // 2. 1234567로 나눈 경우를 더한 뒤 1234567로 나눠서 리턴
        // 피보나치 수열과 같은 점화식 -> 94또는 95번째부터 long의 범위가 넘치기에 나머지로 연산함
        long[] arr = new long[2001];
        
        // 1칸은 1칸만 가는 경우 1개
        arr[1] = 1;
        // 2칸은 1, 1 과 2칸 2개의 경우
        arr[2] = 2;
        
        for(int i = 3; i <=n; i++) {
            arr[i] = (arr[i-2] % 1234567) + (arr[i-1] % 1234567);
        }
        
        return arr[n] % 1234567;
      
    }
    
}

• 이게 왜 피보나치?
  • 피보나치가 아닌 우연의 일치
  • n번째 칸에 도달하는 경우는 아래 2가지 뿐
    • n-2번째 칸에서 2칸 점프
    • n-1번째 칸에서 1칸 점프
  • 따라서 f(n) = f(n-1) 1 + f(n-2) 1의 식을 얻음
    • 1을 곱한 것은 n-2에서 2칸 이동하는 것은 1가지 뿐
    • n-1에서 1칸 이동하는 것은 1가지 뿐
    • 2칸과 1칸을 이동하는 것은 독립적이기에 더함
• 이전 틀린 코드 : dfs로 풀었었는데, 많이 실패함 ㅎㅎ..

class Solution {
    int count = 0;
    public long solution(int n) {
        // 1. n이 1이면 1
        if(n==1) return 1;
        // 2. dfs 탐색 1 또는 2를 계속 더해봄
        dfs(n, 0);
        
        return count;
    }
    
    public void dfs(int target, int cur) {
        if(cur > target)
            return;
        else if(cur == target)
            count++;
        else {
            // 1을 끝까지 더해보고 끝에꺼를 2로 변경해보고 반복
            dfs(target, cur + 1);
            dfs(target, cur + 2);
        }
    }
}

• 출처 : 프로그래머스 - 피보나치로 풀어보신 분들께..