2342-Dance(python)

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

문제를 읽고 먼저 메모리제이션이 떠올랐다. 

현재인덱스, 왼발, 오른발을 저장해야하기에 dp배열을 삼차배열로 만들었다.

그리고 만약 한발자국 바뀔때 두가지 case가 있을 수 있다. 왼발이 가거나 오른발이 가거나.

그때 move함수를 통해 에너지가 어느정도 소요되는지를 구하고 기존의 값에서 더해주는 점화식을 세웠다.

dp데이터에서 다음인덱스는 기존에서 왼발을 움직였을때랑 오른발움직였을때 각각을 저장해주게 됩니다,

dparray를 전부 최대치로 해놓았기 때문에 마지막 인덱스에서 왼발했던거랑 오른발했던거를 비교하여 제일 작은 값으로 출력을 해주게 되면 우리가 찾는 힘을 최소화 하는 방법이 나온다.  더 좋은방법이 있을거라 생각한다. 댓글로 알려주세요

import sys
input = sys.stdin.readline
targetlist = list(map(int,input().split(" ")))
targetnum = len(targetlist)

INF = 1e8
dp = [[[INF for _ in range(5)] for _ in range(5)] for _ in range(targetnum)]
def move(x,y):
    if(x == 0):
        return 2
    elif x==y:
        return 1
    elif abs(x-y)==2 :
        return 4
    else:
        return 3
dp[0][0][0] = 0
for i in range(targetnum-1):
    target = targetlist[i]
    for l in range(5):
        for r in range(5):
            dp[i+1][l][target] = min(dp[i][l][r]+move(r,target), dp[i+1][l][target]) # 오른발 움직이는 경우
            dp[i+1][target][r] = min(dp[i][l][r]+move(l,target), dp[i+1][target][r]) # 왼발
result = INF
for i in range(5):
    for j in range(5):
        result = min(result,dp[len(targetlist)-1][i][j])
print(result)