728x90
2342번: Dance Dance Revolution
입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마
www.acmicpc.net
분석
D[N][L][R] : N개의 수열을 수행한 후 왼발의 위치가 L, 오른발의 위치가 R일 때 최소 누적 힘
mp[i][j] : i에서 j로 이동하는데 드는 힘
- 오른발 : D[N][L][R] = min(D[N-1][L][i] + mp[i][R])
- 왼발 : D[N][L][R] = min(D[N-1][i][R] + mp[i][L])
풀이
import sys
input=sys.stdin.readline
# N개의 열, L 왼발, R 오른발
dp=[[[sys.maxsize for k in range(5)] for j in range(5)] for i in range(100001)]
"""
한 발을 이동할 때 드는 힘 미리 저장
mp[1][2] = 1에서 2로 이동할 때 드는 힘
- 같은 지점 한번 더 1
- 0에서 이동 2
- 인접 지점 3
- 반대편 4
"""
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
l=list(map(int, input().split()))
idx=0
while l[idx]!=0:
n=l[idx]
# 오른발로 이동해 현재 다리 위치로 만들수 있는 경우의 수
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
idx+=1
s-=1 # 마지막 이동 횟수로 idx 조정
result=sys.maxsize
for i in range(5):
for j in range(5):
result=min(result, dp[s][i][j])
print(result)
728x90