🧚‍♂️알고리즘🧚‍♂️ - 동적 계획법(DP) 7

2342번: Dance Dance Revolution

맨 처음에 두 발 0

동시에 움직일 수 없음

 

같은지점 누르기 -> 1

중앙에서 이동 -> 2

인접 위치 이동 -> 3

노인접 위치 이동 -> 4

 

최소 힘으로 누르기

---

D[N][L][R] : N개의 수열 수행 후 왼발 위치 L, 오른발 위치 R 일 때 누적 힘

 

D[N][L][R] =

  D[N-1][L][i] + "i -> R로 이동한 힘"

  D[N-1][i][R] + "i -> L로 이동한 힘"

중 최솟값!

 

오낑

---

import sys
input = sys.stdin.readline

dp = [[[sys.maxsize for k in range (5)] for j in range(5)] for i in range (100001)]
mp = [[0, 2, 2, 2, 2],
       [2, 1, 3, 4, 3], 
       [2, 3, 1, 3, 4],
       [2, 4, 3, 1, 3],
       [2, 3, 4, 3, 1]]

s = 1
dp[0][0][0] = 0

inputList = list(map(int, input().split()))
index = 0

while inputList[index] != 0:
    n = inputList[index]
    for i in range (5):
        if n== i: # 두 발이 같은 자리에 있을 수 없음
            continue
        for j in range (5):
            # 오른발을 옮겨 현재 모습이 됐을 때 최소 힘 저장
            dp[s][i][n] = min(dp[s - 1][i][j] + mp[j][n], dp[s][i][n])
    for j in range (5):
        if n== j: # 두 발이 같은 자리에 있을 수 없음
            continue
        for i in range (5):
            # 왼발을 옮겨 현재 모습이 됐을 때 최소 힘 저장
            dp[s][n][j] = min(dp[s - 1][i][j] + mp[i][n], dp[s][n][j])
    s+= 1
    index += 1

s -= 1 # 마지막 이동 횟수로 index 조정
result = sys.maxsize

for i in range (5):
    for j in range (5) :
        result = min(result, dp[s][i][j]) # 모두 수행한 후 최솟값 찾기
                           
print(result) # 최솟값 출력