Logseq/pages/2342-Dance Dance Revolution.md

• 
• 풀이 1 (재귀함수)

  • import java.util.*;
    
    public class Main {
        static int[][][] dp;
        static int[] inst;
        static int inst_num;
        static int[][] move_energy = {
            {1,2,2,2,2},
            {0,1,3,4,3},
            {0,3,1,3,4},
            {0,4,3,1,3},
            {0,3,4,3,1}
        };
    
        static int solve(int L, int R, int step) {
            if(step == inst_num) return 0;
    
            if(dp[step][L][R] == 0) {
                int target = inst[step];
    
                int moveLeft = solve(target, R, step+1) + move_energy[L][target];
                int moveRight = solve(L, target, step+1) + move_energy[R][target];
    
                dp[step][L][R] = Math.min(moveLeft, moveRight);
            }
    
            return dp[step][L][R];
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            inst = Arrays.stream(sc.nextLine().split(" "))
                               .mapToInt(Integer::parseInt)
                               .toArray();
            sc.close();
    
            inst_num = inst.length-1;
            dp = new int[inst_num][5][5];
    
            System.out.println(solve(0, 0, 0));
        }
    }
    

• 풀이 2 (다이나믹 프로그래밍)

  • import java.util.*;
    
    public class Main {
        static int INF = Integer.MAX_VALUE;
        static int[][] move_energy = {
            {0,2,2,2,2},
            {0,1,3,4,3},
            {0,3,1,3,4},
            {0,4,3,1,3},
            {0,3,4,3,1}
        };
        static int[][][] dp = new int[2][5][5];
        static int curr = 0, next = 1;
    
        static void swap() {
            int temp = curr;
            curr = next;
            next = temp;
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int[] inst = Arrays.stream(sc.nextLine().split(" "))
                               .mapToInt(Integer::parseInt)
                               .toArray();
            sc.close();
    
            for(int i=0; i<2; i++) {
                for(int l=0; l<5; l++) {
                    for(int r=0; r<5; r++) {
                        if(i==0) dp[i][l][r] = INF;
                        else dp[i][l][r] = 0;
                    }
                }
            }
    
            for(int i=inst.length-2; i>=0; i--) {
                int target = inst[i];
                for(int L=0; L<5; L++) {
                    for(int R=0; R<5; R++) {
                        int moveLeft = dp[next][target][R] + move_energy[L][target];
                        int moveRight = dp[next][L][target] + move_energy[R][target];
    
                        dp[curr][L][R] = Math.min(moveLeft, moveRight);
                    }
                }
                swap();
            }
    
            System.out.println(dp[next][0][0]);
        }
    }