[백준 2342번] Dance Dance Revolution (Python3)

import sys
input = sys.stdin.readline
import heapq
INF = 10**9

DDR = list(map(int,input().split()))
DDR.pop()

def force(now,next):
  if now == next:
    return 1
  l1,r1 = foot[now]
  l2,r2 = foot[next]
  set1 = {l1,r1}
  set2 = {l2,r2}
  if set1&set2:
    if (l1+r1+l2+r2)%2 == 1:
      return 3
    else:
      return 4
  return INF

N = len(DDR)

if N == 0:
  print(0)
else:
  DP = [[INF]*(N) for i in range(6)]
  
  foot = [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
  
  check = [[1,1,1,0,0,0],[1,0,0,1,1,0],[0,1,0,1,0,1],[0,0,1,0,1,1]]
  
  for i in range(6):
    if check[DDR[0]-1][i]:
      DP[i][0] = 2
  
  same = True
  for n in range(1,N):
    num = DDR[n]-1
    if num != DDR[0]-1:
      same = False
    for i in range(6):
      if check[num][i]:
        for j in range(6):
          DP[i][n] = min(DP[i][n],DP[j][n-1]+force(j,i))
  
  result = INF
  for i in range(6):
    result = min(result,DP[i][-1])
  
  if same:
    print(result)
  else:
    print(result+1)

 

여러가지로 지저분했던 문제. 풀이도 지저분하고 디버깅도 지저분하고

나만 지저분하게 푼줄 알았더니 다른 사람들도 지저분하게 푼 사람들이 많은 것 같더라... 나정도면 양호한걸지도? ㅋㅋ

 

접근방식은 이러하다. 이 문제는 현 상태에서 발판을 왼발로 밟고있든 오른발로 밟고있든 중요하지 않다. 따라서 1,2,3,4 발판을 밟는 경우의 수를 6가지로 줄일 수 있다. 그리고 각 경우의 수에 0~5까지 번호를 붙인다. foot 리스트와 check리스트가 어느 발판을 밟고있는것인지를 보여준다. (지금 생각해보면 굳이 check리스트를 만들지 말고 in 함수를 쓸걸 그랬다)

 

그리고 force 함수를 통해서 각 경우의 수에서 다른 경우의 수로 넘어갈 때 힘이 몇이 드는지를 계산한다.

 

 

사실 여기까지 하면 아름다운데, 문제는 0을 밟고있는것을 고려해주지 않았다는 것이었다. 그렇다고 이 0 하나때문엔 DP의 수를 10개로 늘리는건 좀 아닌것 같았다. 그러다가 생각한 것이, 어차피 모든 번호가 다 똑같은게 아닌 이상 무조건 두 발 다 발판을 누른다는 것이었다. 그래서 모든 발판의 번호가 다 똑같은 경우와 그렇지 않은 경우를 구별해서 출력하도록 하였다.

 

조금 더럽긴 하지만 그래도 다른 python 제출자들에 비해서 상대적으로 시간이 적게 걸린걸 보니 다른 사람들은 0까지 포함한 DP를(어떤 풀이는 무려 왼발 5가지, 오른발 5가지 총 25개의 DP리스트를 만들었더라)한것 같다.

 

그리고 다른 풀이에서는 Bottom-up이 아닌 Top-down 방식을 많이 사용했는데, 이것도 고려해봐야겠다.

 

 

 

오늘의 교훈) Top-down 방식을 고려하자