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

 

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

2342번: Dance Dance Revolution

 

난이도 : 골드 3
태그 : 다이나믹 프로그래밍

 

 

설명

 

가장 적은 힘을 사용해 DDR을 하는 문제입니다.

음.. 완전탐색을 하기엔 다소 실행 시간이 꽤 걸릴 것 같고,

다이나믹 프로그래밍을 적용시켜볼 수 있겠네요.

 

 

 

접근방법

val dp = Array(n) { Array(5) { Array(5) { Int.MAX_VALUE } } }

 

3차원 배열 하나를 만들었습니다.

dp[index][left][right]로,

해당 인덱스의 (left, right)까지 힘의 최솟값을 저장해놓는 테이블입니다.

 

문제의 예시처럼 1 -> 2 -> 2 -> 4 순서로 움직인다고 했을 때,

초기값 (양발 모두 중앙)에서 오른발을 1로 가거나 왼발을 1로 움직일 수 있습니다.

중앙에서 인접한 곳으로 움직일 때 비용이 2라 명시되어 있으므로, 비용은 2 입니다.

dp[0][1][0] = 2

dp[0][0][1] = 2로 둘 수 있겠습니다.

 

 

1 -> 2 -> 2 -> 4

이제 2를 눌러야 합니다.

기존 (1, 0)에서 (1, 2) 혹은 (2, 0)으로 가는 방법,

기존 (0, 1)에서 (2, 1) 혹은 (0, 2)로 가는 방법이 있습니다.

 

(1, 0)에서 (1, 2) 이동 -> dp[1][1][2] = 기존(dp[0][1][0], 2) + 2 = 4

(1, 0)에서 (2, 0) 이동 -> dp[1][2][0] = 기존(dp[0][1][0], 2) + 3 = 5

(0, 1)에서 (2, 1) 이동 -> dp[1][2][1] = 기존 (dp[0][0][1], 2) + 2 = 4

(0, 1)에서 (0, 2) 이동 -> dp[1][0][2] = 기존 (dp[0][0][1], 2) + 3 = 5

위와 같이 나타낼 수 있습니다.

 

 

1 -> 2 -> 2 -> 4

2를 한 번 더 누를 차례입니다.

기존 단계의 최종 위치들은

 

(2, 0) 비용 5 / (1, 2) 비용 4 / (0, 2) 비용 5 / (2, 1) 비용 4    였습니다.

 

(2, 0)에서 (2, 2) 이동 -> dp[2][2][2] = dp[1][2][0] (5) + 3 = 8

(2, 0)에서 2 한 번 더 누름 -> dp[2][2][0] = dp[1][2][0] (5) + 1 = 6

 

(1, 2)에서 (2, 2) 이동 -> dp[2][2][2] = dp[1][1][2] (4) + 3 = 7, 기존 dp[2][2][2] = 8 보다 작으므로 갱신함

(1, 2)에서 2 한 번 더 누름 -> dp[2][1][2] = dp[1][1][2] (4) + 1 = 5

 

(0, 2)에서 (2, 2) 이동 -> dp[2][2][2] = dp[1][0][2] (5) + 3 = 8, 기존 dp[2][2][2] = 7 보다 크므로 갱신하지 않음

(0, 2)에서 2 한 번 더 누름 -> dp[2][0][2] = dp[1][0][2] (5) + 1 = 6

 

(2, 1)에서 (2, 2) 이동 -> dp[2][2][2] = dp[1][2][1] (4) + 3 = 7, 기존 dp[2][2][2] = 7과 같으므로 갱신하지 않음

(2, 1)에서 2 한 번 더 누름 -> dp[2][2][1] = dp[1][2][1] (4) + 1 = 5

 

위와 같이, 이전 차례의 최종 위치에서 왼발 혹은 오른발을 움직이거나 한 번 더 눌러,

현재 눌러야 하는 번호를 눌렀을 때, 힘의 최솟값을 저장(갱신)합니다.

 

 

1 -> 2 -> 2 -> 4

이전 위치의 최종값은

(0, 2) 비용 6

(1, 2) 비용 5

(2, 0) 비용 6

(2, 1) 비용 5

(2, 2) 비용 7

이였습니다. 이제 각 위치에서 4를 눌렀을 때 최솟값을 구해봅시다.

 

(0, 2)에서 (4, 2) 이동 -> dp[3][4][2] = dp[2][0][2] (6) + 2 = 8

(0, 2)에서 (0, 4) 이동 -> dp[3][0][4] = dp[2][0][2] (6) + 4 = 10

 

(1, 2)에서 (4, 2) 이동 -> dp[3][4][2] = dp[2][1][2] (5) + 3 = 8, 기존 dp[3][4][2] = 8과 같으므로 갱신하지 않음

(1, 2)에서 (1, 4) 이동 -> dp[3][1][4] = dp[2][1][2] (5) + 4 = 9

 

(2, 0)에서 (4, 0) 이동 -> dp[3][4][0] = dp[2][2][0] (6) + 4 = 10

(2, 0)에서 (2, 4) 이동 -> dp[3][2][4] = dp[2][2][0] (6) + 2 = 8

 

(2, 1)에서 (4, 1) 이동 -> dp[3][4][1] = dp[2][2][1] (5) + 4 = 9

(2, 1)에서 (2, 4) 이동 -> dp[3][2][4] = dp[2][2][1] (5) + 3 = 8

 

(2, 2)에서 (4, 2) 이동 -> dp[3][4][2] = dp[2][2][2] (7) + 4 = 11, 기존 dp[3][4][2] = 8 보다 크므로 갱신하지 않음

(2, 2)에서 (2, 4) 이동 -> dp[3][2][4] = dp[2][2][2] (7) + 4 = 11, 기존 dp[3][2][4] = 8 보다 크므로 갱신하지 않음

 

dp[3][2][4] = dp[3][4][2] = 8로

1 -> 2 -> 2 -> 4를 움직이는 최솟값을 찾아냈습니다.

 

 

 

소스코드

import java.util.StringTokenizer
import kotlin.math.abs

fun main() = with(System.`in`.bufferedReader()) {
    val st = StringTokenizer(readLine())

    val n = st.countTokens() - 1
    val dp = Array(n) { Array(5) { Array(5) { Int.MAX_VALUE } } }
    val initial = st.nextToken().toInt()
    dp[0][initial][0] = 2
    dp[0][0][initial] = 2

    var idx = 0

    while (st.hasMoreTokens()) {
        // 1 - 상, 2 - 좌, 3 - 하, 4 - 우
        val cur = st.nextToken().toInt()
        if (cur == 0) break

        for (i in 0..4) {
            for (j in 0..4) {
                if (dp[idx][i][j] == Int.MAX_VALUE) continue
                dp[idx + 1][cur][j] = minOf(dp[idx + 1][cur][j], dp[idx][i][j] + getCost(i, cur))
                dp[idx + 1][i][cur] = minOf(dp[idx + 1][i][cur], dp[idx][i][j] + getCost(j, cur))
            }
        }

        idx++
    }

    var answer = Int.MAX_VALUE

    for (i in 0..4) {
        for (j in 0..4) {
            answer = minOf(answer, dp[idx][i][j])
        }
    }

    println(answer)
}

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

 

getCost는 발을 움직이는 비용을 구하는 함수입니다.

0 (중앙)에서 발을 옮길 땐 비용 2,

같은 칸을 한 번 더 누를 때는 비용 1,

반대칸을 누를 때(번호 차이가 2)는 비용 4,

인접한 칸을 누를 때(나머지 경우)는 비용 3 입니다.

 

 

 

후기

푸는데 걸린 시간보다 포스팅하는데 걸린 시간이 훨씬 많이 든 것 같습니다.

다이나믹 프로그래밍은 푸는 것도 어렵지만 설명 및 정리하는 것도 꽤나 어려운 것 같아요...