백준 2342번 - Dance Dance Revolution

문제

백준 2342번 - Dance Dance Revolution

아이디어

• 한 발로만 계속 움직이거나 발을 번갈아가면서 움직이는 경우에 따라 값이 달라지므로 DP로 모든 경우의 수를 확인하면서 결과를 구한다.
• dp[N][L][R] 을 N번째 수열을 수행한 후, 왼발의 위치가 L, 오른발의 위치가 R일 때 최솟값이라고 정의한다.
• 다른 방향으로 이동할 때 드는 힘을 2차원 배열로 관리한다. arr[i][j]는 i에서 j로 이동하는 데 드는 힘이다.
• 오른발이나 왼발을 움직이는 경우를 구분해서 DP 배열을 채워나간다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BJ_2342 {

    public static final int INF = 999_999;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //i 에서 j 로 이동할 때 드는 힘 초기화
        int[][] arr = {
                {0, 2, 2, 2, 2},
                {2, 1, 3, 4, 3},
                {2, 3, 1, 3, 4},
                {2, 4, 3, 1, 3},
                {2, 3, 4, 3, 1},
        };

        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        int n = input.length;

        int[][][] dp = new int[n][5][5];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    dp[i][j][k] = INF;
                }
            }
        }

        dp[0][0][0] = 0;

        int idx = 0;

        while (input[idx] != 0) {

            //이동 방향
            int point = input[idx];

            for (int i = 0; i < 5; i++) {   //왼발의 위치
                for (int j = 0; j < 5; j++) {   //오른발의 위치

                    //이동 가능한 경로만 탐색
                    if (dp[idx][i][j] == INF) continue;

                    //오른발을 움직이는 경우
                    if (point != i) {   //두 발이 같은 위치에 있는 경우는 보지 않는다.

                        dp[idx + 1][i][point] = Math.min(
                                dp[idx + 1][i][point],
                                dp[idx][i][j] + arr[j][point]
                        );
                    }

                    //왼발을 움직이는 경우
                    if (point != j) {   //두 발이 같은 위치에 있는 경우는 보지 않는다.

                        dp[idx + 1][point][j] = Math.min(
                                dp[idx + 1][point][j],
                                dp[idx][i][j] + arr[i][point]
                        );
                    }
                }
            }

            idx++;
        }

        int ans = INF;

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                ans = Math.min(dp[idx][i][j], ans);
            }
        }

        System.out.println(ans);
    }
}