[Python] 2342 Dance Dance Revolution

💻 문제 정의

다음 모양의 DDR이 있다.

처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다. 하지만 그의 두 발이 동시에 움직이지는 않는다.

이 게임에는 이상한 규칙이 더 있다. 두 발이 같은 지점에 있는 것이 허락되지 않는 것이다. (물론 게임 시작시에는 예외이다) 만약, 한 발이 1의 위치에 있고, 다른 한 발이 3의 위치에 있을 때, 3을 연속으로 눌러야 한다면, 3의 위치에 있는 발로 반복해야 눌러야 한다는 것이다.

중앙에 있던 발이 다른 지점으로 움직일 때, 2의 힘을 사용하게 된다. 그리고 다른 지점에서 인접한 지점으로 움직일 때는 3의 힘을 사용하게 된다. (예를 들면 왼쪽에서 위나 아래로 이동할 때의 이야기이다.) 그리고 반대편으로 움직일때는 4의 힘을 사용하게 된다. (위쪽에서 아래쪽으로, 또는 오른쪽에서 왼쪽으로). 만약 같은 지점을 한번 더 누른다면, 그때는 1의 힘을 사용하게 된다.

💡 접근 및 설계

두 발의 위치 상태를 모두 고려하면서 DP로 접근하였다.

1 → 2 → 1 순서로 발판을 밟는다고 하였을 때, 1을 왼발, 2를 오른발로 밟았을 때, 마지막 1을 왼발로 밟을지, 오른발로 밟을지에 따라 비용이 달라지게 된다. 따라서 그리디 접근이 아닌, DP로 접근해야 한다.

DP 테이블은 dp[i][l][r] 처럼 세울 수 있다. i번째까지의 명령에서, 왼발의 위치 l과 오른발의 위치r 일때 최소 비용을 저장한다.

✏️ 알고리즘 풀이

def cost(a, b):
    if a == 0:
        return 2
    if a == b:
        return 1
    if abs(a-b) == 2:
        return 4
    return 3

현재의 위치에서 다음 위치로 발을 옮길 때 발생하는 비용을 정의한 함수이다.

# 현재 눌러야하는 위치
curr = arr[i]

# 왼발 이동
dp[i+1][curr][r] = min(
    dp[i+1][curr][r],
    cur + cost(l, curr)
)

# 오른발 이동
dp[i+1][l][curr] = min(
    dp[i+1][l][curr],
    cur + cost(r, curr)
)

이전의 상태에서, 현재 눌러야하는 위치를 어느 발로 누를지 모든 경우를 저장하여 최솟값을 비교한다.

최종적으로 마지막 상태에 저장된 값들 중 최솟값을 구하면 된다.

🗒️ 최종 제출 코드

# 2342 Dance Dance Revolution

import sys
# input = sys.stdin.readline

def cost(a, b):
    if a == 0:
        return 2
    if a == b:
        return 1
    if abs(a-b) == 2:
        return 4
    return 3

arr = list(map(int, input().split()))
arr.pop()

INF = 10**9
n = len(arr)

dp = [[[INF] * 5 for _ in range(5)] for _ in range(n+1)]
dp[0][0][0] = 0

for i in range(n):
    curr = arr[i]

    for l in range(5):
        for r in range(5):

            cur = dp[i][l][r]
            if cur == INF:
                continue

            # 왼발 이동
            dp[i+1][curr][r] = min(
                dp[i+1][curr][r],
                cur + cost(l, curr)
            )

            # 오른발 이동
            dp[i+1][l][curr] = min(
                dp[i+1][l][curr],
                cur + cost(r, curr)
            )

ans = INF
for l in range(5):
    for r in range(5):
        ans = min(ans, dp[n][l][r])

print(ans)

---

💭 오늘의 회고

-