Java 1D Array (Part 2) / hackerrank.com

hackerrank.com 의 Java 1D Array (Part 2) 문제를 풀어 보겠습니다.

문제 링크 : https://www.hackerrank.com/challenges/java-1d-array/problem
답 코드 링크 : https://github.com/skysign/WSTT/blob/master/hackerrank/Java%201D%20Array%20(Part%202)/src/com/tistory/skysign/hackerrank/Java_1D_Array_Part_2/Main.java

Discussion에 보면, loop를 사용해서 풀이도 가능한 것으로 보이지만, 요즘 Dynamic Programming을 공부중이기도 하고, 문제를 봤을 때, DP로 풀어보는 방법이 떠올라서, DP로 풀어 보겠습니다.

일종의 DFS방식으로 앞으로 아래 2가지 스텝을 리커젼으로 반복합니다.

• '1칸 전진'
• 'leap 만큼 점프' 를 recursion으로 먼저 해보고,
• 현재 idx가 0인대, 이것을 1로 바꿔서 다시 idx로 오는 것을 방지
• 둘다 실패 하면, '뒤로 한칸 이동' 합니다.

package com.tistory.skysign.hackerrank.Java_1D_Array_Part_2;

import java.util.Scanner;

public class Main {
    public static boolean canWin2(int leap, int[] g, int idx) {
        boolean rA = false, rB = false;
        // idx가 g 보다 크거나 같으면, win
        // g[idx -1] 0인 경우 한칸 더 앞으로 전진해서, idx == g.length 가 되었을 때, win으로 리턴해 줍니다.
        if(idx >= g.length)
            return true;
        // 전진해서 온 칸이 1이라면, 더이상 전진 못하기 때문에 false 리턴
        else if(g[idx] != 0)
            return false;

        // 앞으로 1칸 전진
        rA = canWin2(leap, g, idx +1);
        // leap아 0일 수도 있으므로, 0보다 클 때만,
        if(leap > 0)
            // leap 만큼 jump 합니다.
            rB = canWin2(leap, g, idx +leap);
        // 전진 2가지 방법이 모두 실패 하면,
        if(false == (rA || rB)) {
            // 뒤로 한칸 이동합니다.
            if((0<=idx-1) && (g[idx-1]==0)) {
                // idx에서는 전진 1칸, 전진 leap 점프
                // 모두 해봤는대, 실패 했으므로, g[idx](0)인대, 이를 1로 바꿔서
                // 이후에 다시 시도하지 않도록 합니다.
                g[idx] = 1;
                rB = canWin2(leap, g, idx-1);
            }
        }

        return rA || rB;
    }

    public static boolean canWin(int leap, int[] g) {
        return canWin2(leap, g, 0);
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int q = scan.nextInt();
        while (q-- > 0) {
            int n = scan.nextInt();
            int leap = scan.nextInt();

            int[] game = new int[n];
            for (int i = 0; i < n; i++) {
                game[i] = scan.nextInt();
            }

            System.out.println( (canWin(leap, game)) ? "YES" : "NO" );
        }
        scan.close();
    }
}