2342. Dance Dance Revolution (Python)

 

2342번: Dance Dance Revolution

 

풀이

 3차원 dp를 사용하여 재귀 함수를 통해 답을 구할 수 있다. 3차원 배열인 dp에는 다음과 같은 정보가 저장된다.

dp[left][right][idx] : idx번째 지시사항에서 왼발이 left에 오른발이 right 위치에 있을 때 사용되는 최소의 힘 

 

 왼발과 오른발을 모두 이동시켜가며 dp 배열에 최솟값이 저장되도록 구현해주면 된다. 다만 지시사항이 요구하는 위치가 왼발 또는 오른발과 같은 위치라면 두 발을 모두 이동시킬 필요 없이 같은 위치에 있는 발만 이동시키면 된다. 

 

코드

import sys 
sys.setrecursionlimit(10 ** 6)
INF = float('inf')


def solve(idx, left, right):
    if nums[idx] == 0:
        return 0

    if dp[left][right][idx] != -1: # 이미 기록이 되어 있다면 그대로 리턴 
        return dp[left][right][idx]

    dp[left][right][idx] = INF
    nextStep = nums[idx]

    if nextStep == left: # 다음 지시사항과 왼발의 위치가 같으면 왼발만 이동
        dp[left][right][idx] = min(dp[left][right][idx], solve(idx + 1, left, right) + energy[left][left])
    elif nextStep == right: # 다음 지시사항과 오른발의 위치가 같으면 오른발만 이동 
        dp[left][right][idx] = min(dp[left][right][idx], solve(idx + 1, left, right) + energy[right][right])
    else: # 위치가 모두 다르다면 왼발과 오른발 모두 이동 
        dp[left][right][idx] = min(dp[left][right][idx], solve(idx + 1, nextStep, right) + energy[left][nextStep])  # 왼발 이동
        dp[left][right][idx] = min(dp[left][right][idx], solve(idx + 1, left, nextStep) + energy[right][nextStep])  # 오른발 이동

    return dp[left][right][idx]


if __name__ == '__main__':
    # energy[prev][next] : prev에서 next로 발을 옮길 때 드는 힘 
    energy = [ 
        [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]
    ]

    nums = list(map(int, input().split())) # 입력으로 주어지는 지시 사항 
    # dp[left][right][idx] : idx번째 지시사항에서 왼발이 left에 오른발이 right 위치에 있을 때 사용되는 최소의 힘 
    dp = [[[-1 for _ in range(len(nums))] for _ in range(5)] for _ in range(5)]

    print(solve(0, 0, 0))