[HackerRank] Jumping on the Clouds

출처: https://www.hackerrank.com/challenges/jumping-on-the-clouds/problem

Emma는 한번에 1, 2개의 구름을 건널 수 있으며,

구름 중 [1]은 피해야 하는 구름 / [0]은 건널 수 있는 구름이다.

최소한의 Jumb 횟수로 목적지로 도달하는 경우를 구하는 문제이다.

 Input 
7
0 0 1 0 0 1 0

 Output 

4 　

재귀를 이용해 모든 경우의 수를 구하되, 가장 적게 Jump한 횟수를 도출.　

---

import java.util.Scanner;
 
public class Solution {
     
    static int n, answer;
    static int[] cloud;
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        n = Integer.parseInt(sc.next());
        cloud = new int[n];
         
        for(int i=0; i < n; i++) {
            cloud[i] = Integer.parseInt(sc.next());
        }
         
        answer = n;
        // 현재 위치, 점프 거리, 점프 후 거쳐간 구름 개수(처음과 끝 포함)
        Jump(0, 2, 1);
        Jump(0, 1, 1);
 
 
        System.out.println(answer);
    }
     
    private static void Jump(int idx, int distance, int cnt) {
        int nextIdx = idx + distance;
         
        // 범위 초과 시 return
        if(nextIdx >= n) {
            return;
        }
         
        // 지나갈 수 없는 구름이라면
        if(cloud[nextIdx] > 0) return;
         
        // 끝 지점에 정확히 도착했던 지나쳤던 구름 개수를 비교
        if(nextIdx == n-1) {
            answer = (answer > cnt) ? cnt : answer;
            return;
        }
         
        // 아직 도착 전이라면
        Jump(nextIdx, 2, cnt + 1);
        Jump(nextIdx, 1, cnt + 1);
    }    
}