[Java] 백준 BOJ / 2342번: Dance Dance Revolution

Dance Dance Revolution

문제

---

문제 설명

Dance Dance Revolution 게임을 하는데 발을 움직일 때 얼마나 힘이 드는지 주어진다.

문제에서 주어지는 이동을 전부 해야할 때 드는 최소의 힘을 구하는 문제이다.

---

구현

처음에는 프로그래머스에서 풀었던 키패드 누르기 처럼 그냥 거리를 구해서 그리디 알고리즘 처럼 그때 그때 최선의 선택을 하려 했는데 지금은 최선이여도 나중에 손해를 볼 수 있을 것 같았다.

점화식을 어떻게 세워야할지 몰라서 풀이를 참고 했는데 3차원 DP로 풀어야한다는 것을 알았다.

DP배열은 3차원으로 구성하고 dp[step][left][right] 로 접근해야한다.

step 은 현재 몇 번째 명령을 수행 중인지 확인해준다.

left 와 right 는 각각 왼발, 오른발이 현재 어느 위치에 있는지를 뜻하고 0 ~ 4 의 값을 가질 수 있다.

이렇게 나온 dp[step][left][right] 는 최소 에너지 소비를 뜻한다.

일단 각 위치에서 명령을 수행했을 때의 비용을 계산하기 위해 calculate 라는 함수를 선언했다.

static int calculate(int from, int to) {
	int distance = Math.abs(from - to);
	if (from == 0)
		return 2;
    else if (distance == 0) {
        return 1;
	} else if (distance == 1 || distance == 3)
		return 3;
	else return 4;
}

시작지인 from 이 0이라면 원점에서 출발하기 때문에 2를 리턴하고, 거리가 0이라면 그냥 그 자리를 밟으면 되기 때문에 1을, 거리가 1 또는 3이라면 인접한 방향이기 때문에 3을, 나머지는 4를 리턴하면 된다.

이제 점화식을 세워야 한다. 일단 문제에서 주어진 각 step 마다 반복을 하는 반복문 안에서 진행된다.

각 step에서 왼쪽 발과 오른쪽 발이 갈 수 있는 범위를 확인해야 하기 때문에 left와 right를 모두 0에서 4까지 반복해준다.

다음 밟을 방향은 next 라는 변수로 선언을 해준다.

왼발을 움직여서 next를 밟는 경우는 dp[step + 1][next][right] 에 저장된다.
비교 대상은 이미 저장되어 있을 수 도 있는 dp[step + 1][next][right] 의 값과 현재 위치에서 밟은 최소값인 dp[step][left][right] 값에 left에서 next 까지 드는 힘을 더해준 값이다.

dp[step + 1][next][right] = Math.min(dp[step + 1][next][right], cur + calculate(left, next));

오른발도 마찬가지로 똑같이 구현해주면 된다.

---

코드

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

public class Main_2342 {
    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int[][][] dp;
    static Point left, right;
    static int[] arr;
    static int n;
    static final int INF = 1_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[100001];
        int idx = 0;
        while (true) {
            int num = Integer.parseInt(st.nextToken());
            if (num == 0) break;
            arr[idx++] = num;
        }
        n = idx;

        /**
         * dp[step][left][right] 현재 step 까지 왼발이 left, 오른발이 right 일 때 최소 에너지 소비량
          */
        dp = new int[n + 1][5][5];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 5; j++) {
                Arrays.fill(dp[i][j], INF);
            }
        }
        dp[0][0][0] = 0;

        for (int step = 0; step < n; step++) {
            int next = arr[step];
            for (int left = 0; left < 5; left++) {
                for (int right = 0; right < 5; right++) {
                    int cur = dp[step][left][right];
                    if(cur == INF) continue;

                    dp[step + 1][next][right] = Math.min(dp[step + 1][next][right], cur + calculate(left, next));
                    dp[step + 1][left][next] = Math.min(dp[step + 1][left][next], cur + calculate(right, next));
                }
            }
        }

        int result = INF;
        for (int left = 0; left < 5; left++) {
            for (int right = 0; right < 5; right++) {
                result = Math.min(result, dp[n][left][right]);
            }
        }

        System.out.println(result);

    }

    static int calculate(int from, int to) {
        int distance = Math.abs(from - to);
        if (from == 0)
            return 2;
        else if (distance == 0) {
            return 1;
        } else if (distance == 1 || distance == 3)
            return 3;
        else return 4;
    }
}