[BOJ/DP] 백준 2342 - Dance Dance Revolution (Java)

2342 - Dance Dance Revolution

https://www.acmicpc.net/problem/2342

문제

DDR은 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임
발판은 하나의 중점(0)을 기준으로 위(1), 아래(3), 왼쪽(2), 오른쪽(4)으로 연결되어 있음
처음에 게이머는 두 발을 중앙에 모으고 있음(0 위치)
게임이 시작되면, 지시에 따라 왼쪽/오른쪽으로 발을 움직이는데 두 발이 동시에 움직임 X/ 두 발이 같은 지점에 있는 것 X 
ex. 한 발 1, 다른 한 발 3/ 3을 연속으로 눌러야 함 -> 3의 위치에 있는 발로 반복해서 눌러야 함
발이 움직이는 위치에 따라 드는 힘이 다름
중앙 -> 다른 지점: 2/ 다른 지점 -> 인접한 지점: 3(L -> 위/아래) / 반대편: 4 (L -> 아래/R -> L)/ 같은 지점: 1

입력
지시 사항으로 이뤄지고 각각의 지시 사항은 하나의 수열로 이뤄짐
각각의 수열은 1, 2, 3, 4 숫자로 이뤄지고 이 숫자들은 각각의 방향을 나타냄 (0: 수열의 마지막, 수열 길이 <= 100,000)
출력: 한 줄에 모든 지시 사항을 만족하는 데 사용되는 최소의 합

---

풀이

• `dp[i][j][k]`
  • i: i번째 지시까지 처리했을 때
  • j: 왼발 위치
  • k: 오른발 위치
  • 값: 그 상태깢의 최소 힘

 

초기화

• 모든 상태 불가능(`INF`)로 초기화
• 시작 상태 (0, 0)만 0

int n = arr.size();
int[][][] 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;

 

• i번째 지시에서 `next` 발판 눌러야 함
• 왼발 움직이는 경우: 오른발 이미 `next`에 있으면 X
  • 왼발 j -> `next` / 오른발 k 유지
• 오른발 움직이는 경우: 왼발 이미 `next`에 있으면 X
  • 오른발 k -> `next` / 왼발 j 유지

for (int i = 0; i < n; i++) {
    int next = arr.get(i);

    for (int j = 0; j < 5; j++) {
        for (int k = 0; k < 5; k++) {
            int cur = dp[i][j][k];
            if (cur == INF) continue;

            if (next != k) {
                dp[i + 1][next][k] = Math.min(
                        dp[i + 1][next][k],
                        cur + cost(j, next)
                );
            }

            if (next != j) {
                dp[i + 1][j][next] = Math.min(
                        dp[i + 1][j][next],
                        cur + cost(k, next)
                );
            }
        }
    }
}

 

비용 계산

• 같은 위치: 1
• 중앙(0) -> 이동: 2
• 반대편: 4
• 나머지: 3

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

 

모든 발 위치 조합 중 최솟값

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

---

코드

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

// Dance Dance Revolution
public class boj_2342 {
    static final int INF = 1_000_000_000;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        List<Integer> arr = new ArrayList<>();
        while (true) {
            int x = Integer.parseInt(st.nextToken());
            if (x == 0) break;
            arr.add(x);
        }

        int n = arr.size();
        int[][][] 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 i = 0; i < n; i++) {
            int next = arr.get(i);

            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    int cur = dp[i][j][k];
                    if (cur == INF) continue;

                    if (next != k) {
                        dp[i + 1][next][k] = Math.min(
                                dp[i + 1][next][k],
                                cur + cost(j, next)
                        );
                    }

                    if (next != j) {
                        dp[i + 1][j][next] = Math.min(
                                dp[i + 1][j][next],
                                cur + cost(k, next)
                        );
                    }
                }
            }
        }

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

        System.out.println(min);
    }
}