[백준] 24. Dance Dance Revolution 2342 해설

Dance Dance Revolution

2342번: Dance Dance Revolution

 

80일 넘게 1일 1문제를 풀었던 기록이 깨지게 되었습니다.

문제의 난이도가 올라감에 따라 문제를 못 푸는 빈도가 증가하게 되었는데 이 와중에 하루에 한 문제를 꼭 풀어야 된다는 생각 때문에 문제를 쉽게 포기하고 해설을 보게 된다는 것을 느꼈습니다.

 

이를 방지하고자 못 푸는 문제더라도 최소 이틀의 시간 동안은 생각을 가지고 나서 해설을 보기로 결정하였습니다.

해당 문제도 이와 같은 이유로 이틀 동안 생각을 가졌지만 결국 풀지 못하였습니다.

 

문제

 

풀이

처음 문제를 보고 DP를 이용한 풀이 방법을 찾기 시작하였습니다. 기존 DP풀이처럼 뭔가 계속 쌓이는 규칙을 찾아보았습니다.

하지만 하나의 반례를 충족시키지 못했기 때문에 끝내 문제를 풀 수 없었습니다.

input : 1 4 2 1 0
input : 1 4 2 1 4 0

 

첫 번째 답은 (0, 0) - (1, 0) - (1, 4) - (1, 2) - (1, 2) 으로 2+2+4+1 = 9 가 나옵니다

두 번째 답은 (0, 0) - (1, 0) - (1, 4) - (2, 4) - (1, 4) - (1, 4) 으로 2+2+3+3+1 = 11이 나옵니다.

 

위 두 개의 예시는 이전의 결과가 이후의 결과에 영향을 준다는 점을 반박해 줍니다.

 

이 때문에 결국은 완전탐색을 해줘야 되는 건가 싶었지만

또 막상 완전탐색을 해줄 경우 시간 복잡도가 왼발을 고를 경우와 오른발을 고를 경우로 O(2^n)가 걸리기 때문에 다른 방법을 찾아보게 되었습니다.

 

뭔가 규칙을 찾아줘야 되는가 싶어서 이것저것 모든 방법을 시도하다가 결국 못 풀고 해설을 보게 되었습니다.

 

결과는 완전탐색이 정답이 맞았습니다. 정확히는 DP의 메모이제이션을 이용하여 중복된 탐색을 하지 않는 것으로 O(2^n)의 복잡도를 벗어날 수 있습니다. 

 

 

예시를 보겠습니다. input = [1 4 2 1 0]

왼발 오른발 모든 경우

위 그림은 input 1, 4, 2에 대해서 왼발 오른발의 모든 경우를 보여줍니다. 아무런 조치 없이 위 방식으로 계속 진행된다면 복잡도는 O(2^n)이 됩니다.

 

중복되는 발 위치

하지만 위 그림처럼 동일한 발 위치인 경우가 생기게 됩니다.

input=2인 시점에서 발 위치가 (2,4) 일 때 우리는 굳이 모든 값을 가지지 않고 최솟값만을 가지고 있어 주면 됩니다.

 

 

그러면 실질적으로 위와 같이 경우의 수가 줄어듭니다.

이 말은 즉 아무리 경우의 수가 많아진다 하더라도 해당 범위는 결국 오른발 [0~4] 왼발 [0~4] 총 25가지를 벗어나지 않는다는 점을 알 수 있습니다.

결국 N번의 지시사항이 있을 경우 N X 25으로 정답을 구할 수 있습니다.

중복으로 인해 결국 최대 25의 가지수가 최대이다.

 

 

 

이제 위 데이터를 3차원 배열에 담아준 뒤에 완전탐색을 진행하면 됩니다. 2차원도 버거운데

DP[지시 사항의 개수][왼발][오른발]으로 모든 지시사항을 돌면서 왼발을 바꿔주는 경우와 오른발을 바꿔주는 경우로 완전 탐색을 진행해 주면 됩니다.

 

좀 더 쉬운 이해를 위해 일부 코드를 보면

------------------------------------------------------------------------
idx : 0 1 2 3
val : 1 4 2 1

참고로 초기 발 위치는 (0,0)이기 때문에
dp[0][0][0] = 0 이며
이를 제외한 dp[~][~][~] = MAX으로 초기 설정을 해줘야 됩니다.
------------------------------------------------------------------------
val dp = Array(len) {Array(5) { IntArray(5) {MAX} } }
for (i in 0 until len-1) {  // 모든 지시사항을 돌면서

    val next = input[i]     // i번째 지시사항의 val
    
    for (l in 0..4) {       // 모든 왼발을 돌면서
        for (r in 0..4) {   // l번째 왼발일 때 모든 오른발을 돌면서
        
            // 오른발을 지시사항으로 변경했을 때
            // 즉 모든 왼발의 경우에서 오른발을 변경했을 때 최소값을 구한다.
            dp[i+1][l][next] = Math.min(
            	dp[i+1][l][next], 
                dp[i][l][r] + (r->next 드는 힘) // 이전 위치 + 이동 힘
            )
            
            // 왼발을 지시사항으로 변경했을 때
            // 즉 모든 오른발의 경우에서 왼발을 변경했을 때 최소값을 구한다.
            dp[i+1][next][r] = Math.min(
            	dp[i+1][next][r], 
                dp[i][l][r] + (l->next 드는 힘) // 이전 위치 + 이동 힘
            )
        }
    }
}

 

아래는 전체 코드입니다.

fun main() {

    // 이동 힘에 대한 메서드
    fun energy(pos: Int, des: Int) : Int {
        val num = Math.abs(pos - des)
        return if (pos === 0) 2 else if (num == 0) 1 else if (num == 1 || num == 3) 3 else 4
    }

    val input = readln().split(" ").map { it.toInt() }
    val len = input.size

    val MAX = 1000000
    val dp = Array(len) {Array(5) { IntArray(5) {MAX} } }
    dp[0][0][0] = 0
    
    for (i in 0 until len-1) {
        val next = input[i]
        for (l in 0..4) {
            for (r in 0..4) {
                dp[i+1][l][next] = Math.min(dp[i+1][l][next], dp[i][l][r] + energy(r, next))
                dp[i+1][next][r] = Math.min(dp[i+1][next][r], dp[i][l][r] + energy(l, next))
            }
        }
    }

    // 마지막 지시사항의 모든 발 위치 중 최소값을 구한다.
    // 이게 가능한 이유가 초기값을 MAX로 잡아줬기 때문에 지시사항에 따른 경우만 MAX가 아닌 값이 나온다.
    var result = MAX
    for (l in 0..4) {
        for (r in 0..4) {
            result = Math.min(result, dp[len-1][l][r])
        }
    }
    print(result)
}


/**
 * DP 값 결과 (가독성을 위해 임의로 MAX=100 지정)
 *   0 100 100 100 100  | 100 100 100 100 100  | 100 100 100 100 100  | 100 100 100 100 100  | 100 100 100 100 100  |
 * 100   2 100 100 100  |   2 100 100 100 100  | 100 100 100 100 100  | 100 100 100 100 100  | 100 100 100 100 100  |
 * 100 100 100 100   5  | 100 100 100 100   4  | 100 100 100 100 100  | 100 100 100 100 100  |   5   4 100 100 100  |
 * 100 100   9 100 100  | 100 100   8 100 100  |   9   8 100 100   7  | 100 100 100 100 100  | 100 100   7 100 100  |
 * 100  12 100 100 100  |  12  11   9 100  10  | 100   9 100 100 100  | 100 100 100 100 100  | 100  10 100 100 100  |
 */

 

위에는 bottom-up 방식으로 푼 풀이입니다.

 

top-down방식의 코드도 동일하게 작동하지만 좀 더 가독성이 좋습니다. 하지만 재귀

아래는 top-down 방식의 풀이입니다.

fun main() {

    // 이동 힘에 대한 메서드
    fun energy(pos: Int, des: Int) : Int {
        val num = Math.abs(pos - des)
        return if (pos === 0) 2 else if (num == 0) 1 else if (num == 1 || num == 3) 3 else 4
    }

    val input = readln().split(" ").map { it.toInt() }
    val len = input.size - 1

    val dp = Array(len) {Array(5) { IntArray(5)} }

    fun solve(idx: Int, l: Int, r: Int): Int {
        if (idx == len) return 0  // 지시사항 끝난 경우

        if (dp[idx][l][r] != 0) return dp[idx][l][r]  // 이미 값이 있는 경우 = 중복제거

        val next = input[idx]

        // 왼발을 변경할 경우와 오른발을 변경할 경우 중 최소값을 찾는다.
        dp[idx][l][r] = Math.min(
            solve(idx+1, next, r) + energy(l, next),
            solve(idx+1, l, next) + energy(r, next)
        )

        return dp[idx][l][r]
    }
    print(solve(0,0,0))
}