[2342] Dance Dance Revolution

✔ Dance Dance Revolution

[백준 2342]

문제 분석하기

한 발만 움직여 N개의 수열을 수행할 때

D[N][L][R]의 위치를 만들 수 있는 모든 경우의 수를 비교해 최솟값을 위치에 저장하는 방식으로 문제에 접근

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   
   • D[N][L][R]은 N개의 수열을 수행한 후 왼발의 위치가 L, 오른발의 위치가 R일 때 최소 누적 합
2. 점화식을 구함
   • mp[i][j]가 i에서 j로 이동하는데 드는 힘일 때
   • 바로 직전에 오른발을 움직일 때 D[N][L][R] = MIN(D[N - 1][L][i] + mp[i][R])
   • 바로 직전에 왼발을 움직일 때 D[N][L][R] = MIN(D[N - 1][i][R] + mp[i][L])
   • 왼발과 오른발을 구분해 두 발로 만들 수 있는 모든 경우의 수를 고려해 반복
3. 점화식으로 D 배열을 채운 후 최솟값을 출력

예) 수열 1 2 2 4

시작	중점 : D[0][0][0] = 0
수열 1	중점 → 오른발을 1로 이동(2) D[1][0][1] = 2 중점 → 왼발을 1로 이동(2) D[1][1][0] = 2
수열 1 2	중점 → 오른발을 1로 이동(2)  → 오른발을 2로 이동(3) D[2][0][2] = 5 중점 → 오른발을 1로 이동(2)  → 왼발을 2로 이동(2) D[2][2][1] = 4 중점 → 왼발을 1로 이동(2)  → 오른발을 2로 이동(2) D[2][1][2] = 4 중점 → 왼발을 1로 이동(2)  → 왼발을 2로 이동(3) D[2][2][0] = 5
수열 1 2 2	중점 → 오른발을 1로 이동(2) → 오른발을 2로 이동(3) → 오른발을 2로 이동(1) D[3][0][2] = 6 중점 → 오른발을 1로 이동(2) → 왼발을 2로 이동(2) → 왼발을 2로 이동(1) D[3][2][1] = 5 중점 → 왼발을 1로 이동(2)  → 오른발을 2로 이동(2) → 오른발을 2로 이동(1) D[3][1][2] = 5 중점 → 왼발을 1로 이동(2) → 왼발을 2로 이동(3) → 왼발을 2로 이동(1) D[3][2][0] = 6
수열 1 2 2 4	중점 → 오른발을 1로 이동(2) → 오른발을 2로 이동(3) → 오른발을 2로 이동(1) → 오른발을 4로 이동(4) D[4][0][4] = 10 중점 → 오른발을 1로 이동(2) → 왼발을 2로 이동(2) → 왼발을 2로 이동(1) →  오른발을 4로 이동(3) D[4][2][4] = 8 중점 → 오른발을 1로 이동(2) → 왼발을 2로 이동(2) → 왼발을 2로 이동(1) → 왼발을 4로 이동(4) D[4][4][1] = 9 중점 → 왼발을 1로 이동(2)  → 오른발을 2로 이동(2) → 오른발을 2로 이동(1) → 오른발을 1로 이동(4) D[4][1][4] = 9 중점 → 왼발을 1로 이동(2)  → 오른발을 2로 이동(2) → 오른발을 2로 이동(1) → 왼발을 4로 이동(3) D[4][4][2] = 8 중점 → 왼발을 1로 이동(2) → 왼발을 2로 이동(3) → 왼발을 2로 이동(1) → 왼발을 4로 이동(4) D[4][4][0] = 10

슈도코드 작성하기

D[N][L][R] (N개의 인풋까지 수행했고, 왼쪽 다리가 L, 오른쪽 다리가 R에 있을 때 힘의 최솟값)
mp(한 발을 이동할 때 드는 힘을 미리 저장하기)
D를 충분히 큰 수로 초기화
D[0][0][0]을 0으로 초기화
while(모든 수열이 수행됐을 때까지) {
    for(i -> 0 ~ 4) {
        바로 직전 오른쪽 다리가 있을 수 있는 5가지 경우 누적합 구하기
        D 배열에 오른쪽 다리 이동에 필요한 힘 합산 값 중 최솟값 저장하기
    }
    for(i -> 0 ~ 4) {
        바로 직전 왼쪽 다리가 있을 수 있는 5가지 경우 누적합 구하기
        D 배열에 왼쪽 다리 이동에 필요한 힘 합산 값 중 최솟값 저장하기
    }
}
for(i -> 0 ~ 4) {
    for(j -> 0 ~ 4) {
        min = Math.min(min, D[s][i][j])
    }
}
최솟값 출력하기

코드 구현하기

/**
 * 2342) Dance_Dance_Revolution
 */
public class D093_2342 {
    static int N, S;
    static int D[][][];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // mp(한 발을 이동할 때 드는 힘을 미리 저장하기)
        // {0에서 0, 1, 2, 3, 4로 이동}
        // {1에서 0, 1, 2, 3, 4로 이동}
        // {2에서 0, 1, 2, 3, 4로 이동}
        // {3에서 0, 1, 2, 3, 4로 이동}
        // {4에서 0, 1, 2, 3, 4로 이동}
        int mp[][] = { { 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 } };
        // D[N][L][R] (N개의 인풋까지 수행했고, 왼쪽 다리가 L, 오른쪽 다리가 R에 있을 때 힘의 최솟값)
        D = new int[100001][5][5];
        // D를 충분히 큰 수로 초기화
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 100001; k++) {
                    D[k][i][j] = 100001 * 4;
                }
            }
        }
        // D[0][0][0]을 0으로 초기화 (처음에는 아무 힘도 들지 않은 상태로 시작)
        D[0][0][0] = 0;
        // N(현재 수열의 숫자)
        N = 0;
        // S(현재 수열의 갯수)
        S = 1;
        while (true) {
            // 현재 수열의 숫자 입력
            N = sc.nextInt();
            // 입력의 마지막이면 종료
            if (N == 0)
                break;
            // 오른발(j)을 이동해 현재 발 위치로 만들 수 있는 경우의 수
            for (int i = 0; i < 5; i++) { // D[S][i][j]
                // 두 발이 같은 자리에 있을 수 없음 (이미 왼발이 현재 수열이 숫자에 위치할 경우)
                if (N == i)
                    continue;
                for (int j = 0; j < 5; j++) {
                    // D 배열에 오른발 이동에 필요한 힘 합산 값 중 최솟값 저장하기
                    // 오른발을 옮겨 현재 모습이 됐을 때 최소의 힘
                    D[S][i][N] = Math.min(D[S - 1][i][j] + mp[j][N], D[S][i][N]);
                }
            }
            // 왼발(i)을 이동해 현재 발 위치로 만들 수 있는 경우의 수
            for (int j = 0; j < 5; j++) { // D[S][i][j]
                // 두 발이 같은 자리에 있을 수 없음 (이미 왼발이 현재 수열이 숫자에 위치할 경우)
                if (N == j)
                    continue;
                for (int i = 0; i < 5; i++) {
                    // D 배열에 왼발 이동에 필요한 힘 합산 값 중 최솟값 저장하기
                    // 왼발을 옮겨 현재 모습이 됐을 때 최소의 힘
                    D[S][N][j] = Math.min(D[S - 1][i][j] + mp[i][N], D[S][N][j]);
                }
            }
            S++;
        }
        S--;
        // 모두 수행했을 때 최솟값 찾기
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                min = Math.min(min, D[S][i][j]);
            }
        }
        // 최솟값 출력하기
        System.out.println(min);
    }
}