[백준] 2342번 Dance Dance Revolution (Kotlin)

SeungHyeon·2023년 2월 1일
0

BaekJoon

목록 보기
4/5
post-thumbnail

문제

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

서론

여러분들은 이 문제를 보고 어떤 해결법을 생각하셨나요?

저는 중앙을 기준으로 왼쪽은 왼발이, 우측은 오른발이 밟으면 최소라고 생각했습니다.

그래서 다음과 같이 코드를 작성했었죠

for (i in 1 until list.size) {

    val left = position.left
    val right = position.right

    if (list[i] == 2) { // 왼쪽을 밟는 경우
        dp[i] = when (left) {
            2 -> dp[i - 1] + 1
            0 -> dp[i - 1] + 2
            else -> dp[i - 1] + 3
        }
        position.left = 2
    }

    if (list[i] == 4) { // 오른쪽을 밟는 경우
        dp[i] = when (right) {
            4 -> dp[i - 1] + 1
            0 -> dp[i - 1] + 2
            else -> dp[i - 1] + 3
        }
        position.right = 4
    }

    if (list[i] == 1) { // 위를 밟는 경우
        if (left == 1 || right == 1) {
            dp[i] = dp[i - 1] + 1
        } else if (left == 0) {
            dp[i] = dp[i - 1] + 2
            position.left = 1
        } else if (right == 0) { // 왼쪽 발은 왼쪽 혹은 아래에 위치해 있다.
            dp[i] = dp[i - 1] + 2
            position.right = 1
        } else if (left == 2) {
            dp[i] = dp[i - 1] + 3
            position.left = 1
        } else if (right == 4) { // 왼쪽 발은 아래에만 위치해 있다
            dp[i] = dp[i - 1] + 3
            position.right = 1
        } else { // 모든 발이 아래에만 위치해 있다.
            dp[i] = dp[i - 1] + 4
            position.left = 1
        }
    }

    if (list[i] == 3) { // 아래를 밟는 경우
        if (left == 3 || right == 3) {
            dp[i] = dp[i - 1] + 1
        } else if (left == 0) {
            dp[i] = dp[i - 1] + 2
            position.left = 3
        } else if (right == 0) { // 왼쪽 발은 왼쪽 혹은 위에 위치해 있다.
            dp[i] = dp[i - 1] + 2
            position.right = 3
        } else if (left == 2) {
            dp[i] = dp[i - 1] + 3
            position.left = 3
        } else if (right == 4) { // 왼쪽 발은 위에만 위치해 있다
            dp[i] = dp[i - 1] + 3
            position.right = 3
        } else { // 모든 발이 위에만 위치해 있다.
            dp[i] = dp[i - 1] + 4
            position.left = 3
        }
    }

    if (list[i] == 0) { //가운데를 밟는 경우. 즉 마지막인 경우
        break
    }
}

하지만 이렇게 작성하면 다음과 같은 예시에서 오류를 범하게 됩니다.

1 2

저의 코드에서는 왼발이 1번을 밟고, 다시 왼발이 2번을 밟아 총 5(2 + 3)의 힘이 필요하지만, 실재론 한 발이 1번을 밟고 한 발이 2번을 밟아 4의 힘이 필요해 오류를 범하는 것이죠.

그래서 어떻게 풀었어?

3차원 배열을 이용해 왼발과 오른발의 위치 정보, 그리고 필요한 힘을 저장했습니다.

그리고 다음 단계에서 왼발을 고정하고 오른발로 다음 단계를 밟는 경우와 오른발을 고정하고 왼발로 다음 단계를 밟는 경우 중 최소의 힘을 갱신해줬습니다.

// 왼발만 이동
for (right in 0 until 5) {
    for (left in 0 until 5) {
        dp[i + 1][list[i]][right] = min(dp[i + 1][list[i]][right], dp[i][left][right] + getPower(left, list[i]))
    }
}

// 오른발만 이동
for (left in 0 until 5) {
    for (right in 0 until 5) {
        dp[i + 1][left][list[i]] = min(dp[i + 1][left][list[i]], dp[i][left][right] + getPower(right, list[i]))
    }
}
        

최종 코드

import kotlin.math.abs
import kotlin.math.min

/*
* 백준 2342번. Dance Dance Revolution
* https://www.acmicpc.net/problem/2342
*/

private lateinit var list: ArrayList<Int>
private const val INF = 4 * 100_000 + 1

private fun main() {
    initVariable()
    val result = getResult()
    printResult(result)
}

private fun initVariable() {
    val br = System.`in`.bufferedReader()
    list = br.readLine().split(' ').map { it.toInt() } as ArrayList
    list.removeAt(list.size - 1) // 마지막 0 제거
    br.close()
}

private fun getResult(): Int {
    val dp = dynamicProgramming()
    return getResult(dp)
}

private fun dynamicProgramming(): Array<Array<IntArray>> {

    val dp = Array(size = list.size + 1) { Array(size = 5) { IntArray(size = 5) { INF } } } // n번째, 왼쪽발, 오른쪽발
    dp[0][0][0] = 0 // 처음 위치

    for (i in list.indices) {

        // 왼발만 이동
        for (right in 0 until 5) {
            for (left in 0 until 5) {
                dp[i + 1][list[i]][right] = min(dp[i + 1][list[i]][right], dp[i][left][right] + getPower(left, list[i]))
            }
        }

        // 오른발만 이동
        for (left in 0 until 5) {
            for (right in 0 until 5) {
                dp[i + 1][left][list[i]] = min(dp[i + 1][left][list[i]], dp[i][left][right] + getPower(right, list[i]))
            }
        }
    }

    return dp
}

private fun getPower(from: Int, to: Int): Int {
    return if (from == 0) 2
    else if (from == to) 1
    else if (abs(from - to) == 2) 4
    else 3
}

private fun getResult(dp: Array<Array<IntArray>>): Int {

    var result = Int.MAX_VALUE
    for (left in 0 until 5) {
        for (right in 0 until 5) {
            result = min(result, dp[list.size][left][right])
        }
    }

    return result
}

private fun printResult(result: Int) {
    val bw = System.out.bufferedWriter()
    bw.write("$result\n")
    bw.flush()
    bw.close()
}

참고

profile
어제보다 더 나은 오늘이 되자

0개의 댓글