[BOJ] 2342. Dance Dance Revolution (🥇, DP)

🔗

풀이

왼쪽과 오른쪽 발을 (왼쪽 발, 오른쪽 발)처럼 하나의 좌표로 나타냈을 때 매번 발을 옮길 때마다 가능한 모든 좌표에 대해서 계산해야 한다. 매번 최선의 선택을 한다고 해서 최종적으로 최소가 된다는 것을 보장할 수는 없기 때문이다. 그래서 해당 문제는 그리디가 아니라 DP로 풀 수 있게 된다.

왼쪽과 오른쪽 발이 놓일 수 있는 위치는 0~5로 좌표로 나타내면 5x5크기의 2차원 배열이 된다. 발을 옮기는 횟수는 N번이고 매번 발을 옮길 때마다 5x5의 2차원에 배열에 대한 계산을 하게 되므로 10만x25 = 250만의 연산을 수행하게 된다.

처음 시작은 (0, 0)으로 첫번째로 발을 옮겨야 하는 칸은 x칸이다. 0에서는 어디로 움직여도 2만큼의 힘을 얻게 되므로 (0, x)와 (x, 0)에 각각 값2를 초기화해놓고 시작하면 된다.

import java.util.*;
import java.io.*;

public class Main {
    static int getPower(int s, int e) {
        if (s == 0) return 2;
        if (s == e) return 1;

        if (s == 1) {
            if (e == 3) return 4;
            else return 3;
        } else if (s == 2) {
            if (e == 4) return 4;
            else return 3;
        } else if (s == 3) {
            if (e == 1) return 4;
            else return 3;
        } else {
            if (e == 2) return 4;
            else return 3;
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        List<Integer> arr = new ArrayList<>();
        int input;
        while (true) {
            input = sc.nextInt();
            if (input == 0) break;
            arr.add(input);
        }

        int N = arr.size();
        if (N == 0) System.out.println(0);
        if (N > 0) {
            int[][][] dp = new int[N][5][5];
    
            int next = arr.get(0);
            int left;
            int right;
            int score;
            dp[0][next][0] = 2;
            dp[0][0][next] = 2;
            for (int i = 0; i < N-1; i++) {
                next = arr.get(i+1);
                for (int j = 0; j < 5; j++) {
                    for (int k = 0; k < 5; k++) {
                        score = dp[i][j][k];
                        if (dp[i][j][k] == 0) continue;
                        
                        left = getPower(j, next);
                        right = getPower(k, next);
                        
                        if (dp[i+1][next][k] == 0) {
                            dp[i+1][next][k] = score + left;
                        } else {
                            dp[i+1][next][k] = Math.min(dp[i+1][next][k], score + left);
                        }
                        
                        if (dp[i+1][j][next] == 0) {
                            dp[i+1][j][next] = score + right;
                        } else {
                            dp[i+1][j][next] = Math.min(dp[i+1][j][next], score + right);
                        }
                    }
                }
            }
            int answer = Integer.MAX_VALUE;
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (dp[N-1][i][j] == 0) continue;
                    answer = Math.min(answer, dp[N-1][i][j]);
                }
            }
    
            System.out.println(answer);
        }
    }
}