백준(BOJ) 2342 Dance Dance Revolution(Python)

문제 내용

 

DP 문제.

처음에는 2차원으로 생각해서 풀려고 했는데 안 돼서 3차원으로 풀었다.

각 시행마다 오른발, 왼발이 놓인 위치를 DP로 구현했다.

5*5*100000이라 꽤 여유있었다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

L=list(map(int,input().split()))
INF=10e9
dp=[[[INF for k in range(5)] for j in range(5)] for i in range(len(L))]
check={1:3,2:4,3:1,4:2}
dp[0][0][0]=0
for i in range(1,len(L)):
    p=L[i-1]
    for j in range(5):
        for k in range(5):
            x=dp[i-1][j][k]
            if x<INF:
                if p!=k:
                    if j==0:
                        dp[i][p][k]=min(dp[i][p][k],x+2)
                    elif p==check[j]:
                        dp[i][p][k]=min(dp[i][p][k],x+4)
                    else:
                        dp[i][p][k]=min(dp[i][p][k],x+3)
                else:
                    dp[i][j][k]=min(dp[i][j][k],x+1)
                if p!=j:
                    if k==0:
                        dp[i][j][p]=min(dp[i][j][p],x+2)
                    elif p==check[k]:
                        dp[i][j][p]=min(dp[i][j][p],x+4)
                    else:
                        dp[i][j][p]=min(dp[i][j][p],x+3)
                else:
                    dp[i][j][k]=min(dp[i][j][k],x+1)
ans=INF
for i in range(5):
    k=min(dp[-1][i])
    ans=min(k,ans)
print(ans)

그나마 숨 좀 돌릴 만한 문제였다.