[백준 파이썬] 2342 Dance Dance Revolution

백준 2342

다음 스탭을 밟을 때 필요한 힘은 왼쪽 발이나 오른쪽 발을 옮겼을 때 드는 비용의 최솟값이다.

현재 위치에서 항상 최소 비용을 가지는 방향으로 그리디하게 푼다면
move = [1, 4, 2, 1, 1, 0] 로 들어 왔을 때
(1, 0) → (1, 4) → (2, 4) → (1, 4) → (1, 4)로 총 11이 소모된다.
하지만
(1, 0) → (1, 4) → (1, 2) → (1, 2) → (1, 2)로 이동하게 된다면 10이 소모되어 더 적은 힘이 필요하게 된다.

이는 가장 마지막 스탭에서 처음으로 돌아오면서 비용을 비교하고 값을 추가해주면 된다. 재귀로 구현하면 다음과 같다.
dp(i 번째 스탭, 왼발의 위치, 오른발의 위치)

from functools import cache

move = [0] + list(map(int, input().split()))
weight = [ # row 번째 있던 발을 col 번째로 옮길 경우 필요한 힘
    [0, 2, 2, 2, 2],
    [0, 1, 3, 4, 3],
    [0, 3, 1, 3, 4],
    [0, 4, 3, 1, 3],
    [0, 3, 4, 3, 1],
]

@cache # 메모이제이션을 위한 데코레이터
def dp(cur, left, right):
    if cur == len(move)-1: # 가장 마지막 스탭은 0이 입력되므로 0 반환
        return 0
    if left != 0 and right != 0 and left == right: # 두 발이 같은 위치에 있으면 안된다
        return 10**9
    else:
    	# 재귀문을 빠져나오면서 왼발이나 오른발을 옮겼을 때 비용의 최솟값이 반환된다
        # ex) dp(다음, 왼발을 move의 다음 위치로 이동, 오른발은 유지) + 왼발을 move의 다음 위치로 옮길 때 필요한 힘
        return min(dp(cur+1, move[cur+1], right) + weight[left][move[cur+1]], 
                   dp(cur+1, left, move[cur+1]) + weight[right][move[cur+1]])
    
print(dp(0, 0, 0))

functools.cache 설명