[백준] 2342번 - Dance Dance Revolution (Java)

문제

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

2342번: Dance Dance Revolution

 

입력

 

출력

---

알고리즘

다이나믹 프로그래밍

 

각 쿼리처리 시점에서 왼발과 오른발 위치에 따른 힘의 최솟값을 계속 기록해두고 출력하면 된다.

 

dp[i][j][k] : i번째 DDR 쿼리를 처리하는 시점에서, 왼발이 j에 있고 오른발이 k에 있을때 힘의 최솟값

이라고 dp테이블을 정의해보자. 여기에 쿼리가 아래와 같이 주어진다고 예시를 들어보자

 

1 2 2 4 0

 

쿼리가 1번째부터 시작한다고 가정하면, dp[0][0][0]이면 초기 시점의 힘의 최솟값을 의미하는 것이고, dp[2][1][2]는 2번째 쿼리, 즉 2를 누를려고 할때 왼발이 1에 있고 오른발이 2에 있을때 힘의 최솟값을 의미한다. dp[4][3][4]면 4번째 쿼리, 즉 4를 누를려고 할때 왼발이 3에 있고 오른발이 4에 있을때 힘의 최솟값을 의미한다. 힘의 최솟값을 구하는 것이므로 dp의 모든 값을 최댓값으로 설정해주고, 초기에는 양발 모두 중앙에 있다고 했으므로 dp[0][0][0]만 0으로 설정해준다. 이때, 최댓값을 설정할때 Integer.MAX_VALUE로 설정을 해버리면 더하는 과정에서 오버플로우가 나버리니 최댓값보다 살짝 작은 값으로 설정해줘야 정상적으로 답이 나온다.

 

점화식은 우선 i번째 DDR 버튼을 누르기 위해서는 왼발을 움직여 눌러도 되고 오른발을 움직여 눌러도 된다. 따라서, 왼발을 누를경우와 오른발을 누를 경우를 각각 점화식을 세워줘야 한다.

 

next = query.get(i-1) : 다음에 누를 DDR의 버튼 번호

dp[i][next][k] = Math.min(dp[i][next][k], dp[i-1][j][k] + distance(j, next)) : 왼발을 j위치에서 next를 누르기 위해서 이동하기 위해 드는 힘

dp[i][j][next] = Math.min(dp[i][j][next], dp[i-1][j][k] + distance(k, next)) : 오른발을 k위치에서 next를 누르기 위해서 이동하기 위해 드는 힘

 

이렇게 설정해준다. 또한, 문제 조건에서 처음을 제외하고 두 발이 모두 같은 위치에 있는 것이 허락되지 않는 다는 규칙이 있다. 따라서, 두 발이 모두 같은 위치로 가는 경우는 제외하고 dp테이블을 갱신시켜줘야 한다.

 

그 다음, 이동하는데 드는 힘을 계산해주기 위해서 distance 함수를 만들었는데

위에 주석에 써있는 것과 같이 각 경우에 따라서 힘의 값을 리턴해주면 된다.

이렇게 모든 값을 갱신했으면 n번째 쿼리를 처리했을때 모든 값 중에서 제일 작은 것을 출력해주면 답이 된다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        ArrayList<Integer> query = new ArrayList<>();

        //DDR 쿼리 저장
        while(true){
            int tmp = Integer.parseInt(st.nextToken());
            if(tmp == 0) break;
            query.add(tmp);
        }

        int n = query.size();
        //dp[i][j][k] : i번째 DDR 쿼리를 처리하는 시점에서, 왼발이 j에 있고 오른발이 k에 있을때 힘의 최솟값
        int[][][] dp = new int[n+1][5][5];

        //최솟값을 구하는 것이니 최댓값으로 초기화. 이때, MAX_VALUE로 해버리면 오버플로우가 날 수도 있으니 적당히 큰값으로
        for(int i = 0; i<n+1; i++){
            for(int j = 0; j<5; j++){
                for(int k = 0; k<5; k++){
                    dp[i][j][k] = 2147483643;
                }
            }
        }

        //초기에는 두 발 모두 중앙에 있다고 했고 그때는 힘이 0이다.
        dp[0][0][0] = 0;

        for(int i = 1; i<n+1; i++){
            int next = query.get(i-1);

            for(int j = 0; j<5; j++){
                for(int k = 0; k<5; k++){
                    //(i-1)번째에서 왼발을 j위치에서 next로 옮기는 경우 힘의 최솟값 (양발이 같은 위치로 가는 경우 제외)
                    if(next != k) dp[i][next][k] = Math.min(dp[i][next][k], dp[i-1][j][k] + distance(j, next));
                    //(i-1)번째에서 오른발을 k위치에서 next로 옮기는 경우 힘의 최솟값 (양발이 같은 위치로 가는 경우 제외)
                    if(next != j) dp[i][j][next] = Math.min(dp[i][j][next], dp[i-1][j][k] + distance(k, next));
                }
            }
        }

        int min = Integer.MAX_VALUE;

        //제일 작은 값을 찾는다
        for(int j = 0; j<5; j++){
            for(int k = 0; k<5; k++){
                min = Math.min(dp[n][j][k],min);
            }
        }


        System.out.println(min);
    }

    //before은 이동하기 전의 위치, after는 오른발의 위치
    public static int distance(int before, int after){
        //before와 after가 같으면 제자리를 한번 더 누른 것이기 때문에 힘이 1
        if(before == after) return 1;
        //before가 0이었다면 중앙에서 이동한 것이므로 힘이 2
        else if(before == 0) return 2;
        //before와 after의 차이 절댓값이 4라면 완전 반대 방향으로 움직인 것이므로 힘이 4
        else if(Math.abs(before-after) == 2) return 4;
        //나머지 경우는 힘이 3
        else return 3;
    }
}