[BaekJoon] 2342 Dance Dance Revolution (Java)

1.  문제 링크

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

2.  문제

요약

• DDR은 발판에서 주어진 스텝에 맞춰 나가는 게임인데, 발판은 하나의 중점을 기준으로 위, 아래, 왼쪽, 오른쪽으로 연결되어 있습니다. 편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4로 가정합니다.
• 게이머는 두 발을 중앙에 모으고 있다가 게임이 시작되면 지시에 따라 왼쪽 또는 오른쪽 발을 움직이는데, 두 발이 동시에 움직이지는 않습니다.
• 두 발이 같은 지점에 있는 것은 게임 시작시를 제외하고는 허락되지 않고, 한 위치를 연속으로 눌러야 할 때 해당 위치에 발이 위치해있다면 해당 발로 반복해서 누릅니다.
• 발이 움직이는 위치에 따라서 드는 힘이 다릅니다.
  • 중앙에 있던 발이 다른 지점으로 움직일 때, 2의 힘을 사용합니다.
  • 다른 지점에서 인접한 지점으로 움직일 때 3의 힘을 사용합니다.
    • 반대편으로 움직일 때 4의 힘을 사용합니다.
• 지시 사항이 주어질 때, 모든 지시 사항을 만족하는 데 사용되는 최소의 힘을 구하는 문제입니다.
• 입력: 첫 번째 줄에 지시 사항이 주어집니다. 각각의 지시 사항은 하나의 수열로 이루어집니다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타냅니다. 0은 수열의 마지막을 의미합니다. 즉, 입력 파일의 마지막에는 0이 입력됩니다. 입력되는 수열의 길이는 100,000을 넘지 않습니다.
• 출력: 첫 번째 줄에 모든 지시 사항을 만족하는 데에 사용되는 최소의 힘을 출력합니다.

3.  소스코드

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

public class Main {
    static ArrayList<Integer> moveLocs;
    static int[][][] dp;

    static void input() {
        Reader scanner = new Reader();

        moveLocs = new ArrayList<>();
        while(true) {
            int loc = scanner.nextInt();
            if(loc == 0) break;
            moveLocs.add(loc);
        }
    }

    static void solution() {
        dp = new int[5][5][moveLocs.size()];
        for(int row = 0; row < 5; row++) {
            for(int col = 0; col < 5; col++)
                Arrays.fill(dp[row][col], -1);
        }

        System.out.println(findMinStrength(0, 0, 0));
    }

    static int findMinStrength(int left, int right, int count) {
        if(count == moveLocs.size()) return 0;

        if(dp[left][right][count] != -1) return dp[left][right][count];

        dp[left][right][count] = Math.min(
                findMinStrength(moveLocs.get(count), right, count + 1) + getNecessaryStrength(left, moveLocs.get(count)),
                findMinStrength(left, moveLocs.get(count), count + 1) + getNecessaryStrength(right, moveLocs.get(count))
        );

        return dp[left][right][count];
    }

    static int getNecessaryStrength(int curLoc, int destLoc) {
        if(curLoc == 0) return 2;

        int num = Math.abs(curLoc - destLoc);

        if(num == 0) return 1;
        else if(num == 1 || num == 3) return 3;
        else return 4;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 사용되는 최소 힘을 구하기 위해 2차원 배열 dp를 생성합니다.
  • dp[left][right][count] = 지시 사항의 (count + 1)번째 위치에서 왼발이 left 위치에, 오른발이 right 위치에 있을 때의 사용되는 최소 힘
  • 초기에는 모든 값을 -1로 초기화합니다.
• 처음에는 왼발과 오른발 모두 중앙에 위치하므로 왼발과 오른발 모두 0의 위치에서 시작합니다.
• 다음 위치로 이동하기 위해 왼발을 움직이는 경우와 오른발을 움직이는 경우가 존재합니다.
• 재귀를 이용해 왼발로 움직이는 경우에 필요한 힘과 오른발로 움직이는 경우에 필요한 힘을 구합니다.
• 왼발로 움직인 경우와 오른발로 움직인 경우에 사용되는 힘을 비교하여 더 작은 힘을 dp[left][right][count]에 저장합니다.
• dp 배열에 있는 값을 이용하여 최종적으로 왼발로 움직인 경우와 오른발로 움직인 경우에 사용되는 힘 중 더 작은 힘을 선택해 해당 값을 반환합니다.