[Python] boj no. 2342 : Dance Dance Revolution

Problem

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

Idea

i번째 지시사항에 따라 이동했을 때의 발의 위치가 0번째부터 i-1번째 지시사항을 이행하면서 얻은 발의 위치에 영향을 받으므로 다이나믹 프로그래밍 문제라고 생각했다.

dp를 위해 3차원 배열 dp[index][왼발의 위치 == 5][오른발의 위치 == 5]를 선언한다. 이후 루프문을 통해 게임의 지시사항을 수행한다. 이 때, i번째 지시사항을 수행하기 위해 두 가지 방법이 존재한다. 오른발을 지시 위치로 옮기거나 왼발을 지시 위치로 옮기는 것이다.

왼발을 지시 위치로 옮기는 케이스에서는 왼발의 최종 위치는 고정되어 있지만 오른발의 위치는 자유롭다. 따라서 왼발의 좌표는 고정한 채로 오른발의 좌표만 바꾸어가며 dp 배열을 갱신시킨다. 이 때, dp 갱신을 위해 이전에 구한 i-1번째의 dp 배열과 이전 좌표를 이용하여 최소값으로 갱신한다.

왼발과 오른발 각각을 옮기는 케이스를 모두 구하면 dp배열에는 i번째 지시사항을 수행했을 때 dp[i][l][r]은 왼쪽 발 위치가 l, 오른발 위치가 r인 상황의 최소비용이 된다.

Code

import sys

def moved(s, e):
    if s == e:
        return 1
    elif s == 0:
        return 2
    elif abs(s - e) == 2:
        return 4
    else:
        return 3

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

dp = [[[sys.maxsize for _ in range(5)] for _ in range(5)] for _ in range(len(command)+1)] # idx, left, right

dp[0][0][0] = 0

for i, c in enumerate(command, start=1):
    # 왼발이 c로 이동
    for r in range(5):
        for l in range(5):
            dp[i][c][r] = min(dp[i][c][r], dp[i-1][l][r] + moved(l, c))
    
    # 오른발이 c로 이동        
    for l in range(5):
        for r in range(5):
            dp[i][l][c] = min(dp[i][l][c], dp[i-1][l][r] + moved(r, c))

print(min(list(map(min, dp[len(command)]))))

Comment