[백준] Q2342 Dance Dance Revolution JAVA

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

2342번: Dance Dance Revolution

1. 문제 유형 및 이해

dp

발판을 기준으로 주어지는 수열에 따라 발을 움직여 방향을 맞추어야 한다.

발을 움직일 때는 움직이는 방법에 따라 드는 힘이 다르다.

이 때, 주어지는 수열을 만족시키면서 힘을 가장 적게 사용했을 때의 힘을 찾아보자.

 

처음에는 그리디라고 생각을 하고 접근해서 순간의 최선을 선택하려고 했다.

하지만, 발이 움직이는 방향에 따라 드는 힘이 다르기 때문에 현재의 최선이 전체의 최선이 되지 못함을 알았다.

예를 들어 인접해서 두번 (3,3) 하는 것과 반대로 옮겨서 제자리에서 누르게 되는 경우(4,1)를 비교하면, 현재의 최선은 3이지만 전체의 최선에서는 반대편으로 옮기는 것이 맞기 때문에 그리디하지 않다는 것을 알았다.

 

그렇다면, 결국 그 전 상태에 따라 현 상태를 결정하도록 모든 방법에 대해 탐색해야하는데, 이 때 중복이 발생할 수 있으므로 dp를 사용하면서 memo를 해두는 방식으로 진행했다.

2. 문제 접근 방법

dp배열을 정의할 때 왼쪽발, 오른쪽 발의 위치를 알아야하고 그 전 순서에 영향을 받기 때문에

dp[left][right][step]으로 정의했다.

dp[left][right][step] = 현재 step에서 각 발 위치에 따라 최소값

 

또한 생각해야할 건, 현재 밟아야하는 방향이 들어오면, 왼발이든 오른발이든 누구하나는 밟아야 한다는 점이다.

즉, 어떤 상태에서 왼발이 움직이는 경우와 오른발이 움직이는 경우 두가지 경우로 나뉘게 된다.

 

가장 쉽게 떠올릴 수 있는 방법은 역시 top-down이였던 것 같다.

 2.1 top - down

dp[left][right][step] = Math.min(왼발을 움직였을 때 힘, 오른발을 움직였을 때 힘)

 2.2 bottom-up

순차적으로 채워나간다.

문제에서 같은 곳에 두 발이 있을 수 없다고 했으므로 이를 고려하며 모든 경우에 대해 분기해준다.

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

/**
 * @author : pcrmcw0486
 * @문제번호 : Review_2342
 * @문제이름 : Dance Dance Revolution
 * @난이도 : Gold 3
 * @date : 2022-03-08 오전 11:14
 * @문제이해
 * @알고리즘
 * @접근방법
 */
public class Main {
    static int INF = 444444;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] data = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[][][] dp = new int[data.length][5][5];
        int size = dp.length-1;
        for (int[][] d : dp)
            for (int[] p : d)
                Arrays.fill(p, INF);

        dp[0][0][0] = 0;
        int ans =INF ;
        int prevPos =0;
        for(int i =1; i<data.length;i++){
            int next = data[i-1];
            for (int l = 0; l < 5; l++) {
                for (int r = 0; r < 5; r++) {
                    int v = dp[i-1][l][r];
                    if (l != next)
                        dp[i][l][next] = Math.min(dp[i][l][next], v + getMove(r, next));
                    if(r != next)
                        dp[i][next][r] = Math.min(dp[i][next][r], v + getMove(l, next));
                }
            }

        }
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                ans = Math.min(ans, dp[dp.length-1][i][j]);
            }
        }
        System.out.println(ans);
    }

    private static int getMove(int a, int b) {
        if (a == 0 || b == 0) return 2;
        if (a == b) return 1;
        else if (((a+1) % 4) == b-1) return 4;
        return 3;
    }
}