[BOJ] Dance Dance Revolution - 2342

🎨 문제

2342번: Dance Dance Revolution

📘 풀이

DP와 분할정복을 혼합하여 풀었습니다.

완전 탐색의 경우 왼발과 오른발을 쓰는 지(두가지)와 입력 수열의 길이가 100,000이 최대이므로 시간 복잡도가 2의 100,000제곱으로 TLE가 발생합니다. 

 

DP 배열

DP = int[눌러야하는 발판][왼발 위치][오른발 위치]

 

눌러야할 발판은 입력받은 배열의 길이입니다. 마지막 발판은 0이므로 1을 빼주어도 됩니다.

발의 위치는 다섯가지로 중앙, 위, 아래, 왼쪽, 오른쪽입니다.

 

현재 발판에서 어떤 발로 어떤 발판을 누르면 얼마의 힘이 드는지를 저장하는 것입니다. 뒤쪽에 예시를 보면 조금 더 잘 이해될 것입니다.

분할정복

FootBoard next = SEQUENCE.get(step);
// 왼발 이동
int leftPower = leftFoot.move(next) + dfs(next, rightFoot, step + 1);

// 오른발 이동
int rightPower = rightFoot.move(next) + dfs(leftFoot, next, step + 1);

return DP[step][leftFoot.getNumber()][rightFoot.getNumber()] = Math.min(leftPower, rightPower);

1. 이동해야할 발판을 구합니다.
2. 현재 위치에서 왼발을 사용해 이동했을 경우 사용하는 힘을 구합니다.
3. 현재 위치에서 오른발을 사용해 이동했을 경우 사용하는 힘을 구합니다.
4. 둘 중 작은 값을 반환합니다.

가지치기

DP 배열이 이미 초기화되었다면 가지치기를 합니다.

왼발과 오른발을 바꿔도 동일한 결과를 얻기 때문에 가지치기합니다.

// 이미 초기화된 경우 가지치기
if (DP[step][leftFoot.getNumber()][rightFoot.getNumber()] != 0) {
    return DP[step][leftFoot.getNumber()][rightFoot.getNumber()];
}

// 발을 바꾼 경우에 이미 초기화된 경우 가지치기
if (DP[step][rightFoot.getNumber()][leftFoot.getNumber()] != 0) {
    return DP[step][rightFoot.getNumber()][leftFoot.getNumber()];
}

발판

발판의 경우의 수가 정해져 있어 enum을 사용해 구현해 보았습니다.

enum FootBoard {
    START(0), UP(1), DOWN(3), LEFT(2), RIGHT(4);

    private final int number;

    FootBoard(int number) {
        this.number = number;
    }

    public static FootBoard footBoardFromNumber(int number) {
        return Arrays.stream(FootBoard.values())
                .filter(footBoard -> footBoard.number == number)
                .findAny()
                .orElseThrow();
    }

    public int getNumber() {
        return number;
    }

    private boolean isOpposite(FootBoard footBoard) {
        return Math.abs(this.number - footBoard.number) == 2;
    }

    private boolean isAdjacency(FootBoard footBoard) {
        if (this == START) {
            return false;
        }

        int offset = Math.abs(this.number - footBoard.number);

        return offset == 1 || offset == 3;
    }

    private int move(FootBoard moveBoard) {

        // 중앙 지점에서 다른 지점으로
        if (this == START) {
            return 2;
        }

        // 동일한 지점
        if (this == moveBoard) {
            return 1;
        }

        // 인접한 지점
        if (this.isAdjacency(moveBoard)) {
            return 3;
        }

        // 반대 지점
        if (this.isOpposite(moveBoard)) {
            return 4;
        }

        throw new IllegalArgumentException();
    }
}

📒 예시

문제의 예시를 가져왔습니다.

입력

1 2 2 4 0

enum으로 표현하면

START ➡ UP ➡ LEFT ➡ LEFT ➡RIGHT

출력

8

DP 배열

배열 전체

총 네 번 움직이기 때문에 네 개의 2차원 배열이 생깁니다. 각 2차원  하나씩 보겠습니다.

첫 번째 배열

첫 번째 배열

밟아야할 발판: UP ➡ LEFT ➡ LEFT ➡RIGHT
(START, START)에서 마지막 발판까지 밟았을 때 최소값이 8이라는 의미입니다.

두 번째 배열

두 번째 배열

밟아야할 발판: LEFT ➡ LEFT ➡RIGHT

(UP, START), (START, UP) 에서 마지막 발판까지 밟았을 때 최소값이 6

세 번째 배열

세 번째 배열

밟아야할 발판: LEFT ➡RIGHT

(START, LEFT), (LEFT, START)에서 마지막 발판까지 밟았을 때 최소값이 3

(UP,LEFT), (LEFT,UP)에서 마지막 발판까지 밟았을 때 최소값이 4

네 번째 배열

네 번째 배열

밟아야할 발판: RIGHT

(START, LEFT), (LEFT, START)에서 마지막 발판까지 밟았을 때 2

(UP,LEFT), (LEFT,UP)에서 마지막 발판까지 밟았을 때 3

(LEFT, LEFT) 에서 마지막 발판까지 밟았을 때 4

 

Bottom up 방식으로 작은 문제부터 해결합니다.

결국 (START, START)에 최소값이 저장됩니다.

📗 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Main {

    static List<FootBoard> SEQUENCE;
    static int[][][] DP;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        SEQUENCE = Arrays.stream(br.readLine().split(" "))
                .map(Integer::valueOf)
                .map(FootBoard::footBoardFromNumber)
                .collect(Collectors.toList());
        int steps = FootBoard.values().length;
        DP = new int[SEQUENCE.size() - 1][steps][steps];

        int answer = dfs(FootBoard.START, FootBoard.START, 0);

        System.out.println(answer);
    }

    private static int dfs(FootBoard leftFoot, FootBoard rightFoot, int step) {

        // 마지막까지 탐색후 종료
        if (step == SEQUENCE.size() - 1) {
            return 0;
        }

        // 이미 초기화된 경우 가지치기
        if (DP[step][leftFoot.getNumber()][rightFoot.getNumber()] != 0) {
            return DP[step][leftFoot.getNumber()][rightFoot.getNumber()];
        }

        // 발을 바꾼 경우에 이미 초기화된 경우 가지치기
        if (DP[step][rightFoot.getNumber()][leftFoot.getNumber()] != 0) {
            return DP[step][rightFoot.getNumber()][leftFoot.getNumber()];
        }

        FootBoard next = SEQUENCE.get(step);

        // 왼발 이동
        int leftPower = leftFoot.move(next) + dfs(next, rightFoot, step + 1);

        // 오른발 이동
        int rightPower = rightFoot.move(next) + dfs(leftFoot, next, step + 1);

        return DP[step][leftFoot.getNumber()][rightFoot.getNumber()] = Math.min(leftPower, rightPower);
    }

    enum FootBoard {
        START(0), UP(1), DOWN(3), LEFT(2), RIGHT(4);

        private final int number;

        FootBoard(int number) {
            this.number = number;
        }

        public static FootBoard footBoardFromNumber(int number) {
            return Arrays.stream(FootBoard.values())
                    .filter(footBoard -> footBoard.number == number)
                    .findAny()
                    .orElseThrow();
        }

        public int getNumber() {
            return number;
        }

        private boolean isOpposite(FootBoard footBoard) {
            return Math.abs(this.number - footBoard.number) == 2;
        }

        private boolean isAdjacency(FootBoard footBoard) {
            if (this == START) {
                return false;
            }

            int offset = Math.abs(this.number - footBoard.number);

            return offset == 1 || offset == 3;
        }

        private int move(FootBoard moveBoard) {

            // 중앙 지점에서 다른 지점으로
            if (this == START) {
                return 2;
            }

            // 동일한 지점
            if (this == moveBoard) {
                return 1;
            }

            // 인접한 지점
            if (this.isAdjacency(moveBoard)) {
                return 3;
            }

            // 반대 지점
            if (this.isOpposite(moveBoard)) {
                return 4;
            }

            throw new IllegalArgumentException();
        }
    }
}