[다이나믹 프로그래밍 / 파이썬] 백준 2342번 : Dance Dance Revolution / 골드 3

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

2342번: Dance Dance Revolution

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

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

inf = 9876543210

# dp[i][left][right]
dp = [[[inf for _ in range(5)] for _ in range(5)] for _ in range(len(command))]
dp[0][0][0] = 0

for i in range(1, len(command)):
    cur = command[i-1]  # 지금 밟아야 하는 위치

    # j : 움직이지 않은 발의 위치
    # k : 움직인 발의 이전 위치
    for j in range(5):
        left = inf
        right = inf
        for k in range(5):
            left = min(left, dp[i-1][k][j] + score(k, cur))  # 왼발을 움직였을 때
            right = min(right, dp[i-1][j][k] + score(k, cur))  # 오른발을 움직였을 때
        dp[i][cur][j] = left
        dp[i][j][cur] = right

answer = inf
for i in range(5):
    for j in range(5):
        answer = min(answer, dp[-1][i][j])
print(answer)

약 8개월 전에 시도했다가 못풀었는데, 이번에 드디어 해결하게 되었다.

고민은 굉장히 많이 했는데 답은 오히려 간단히 나왔다.

 

처음에는 여러가지 경우의 수를 따져 조건을 분기하려했으나 어차피 dp 값을 무한대로 초기화해놓으면

굳이 따져주지 않아도 최솟값을 찾는 과정에서 자연스럽게 걸러진다.