Dance Dance Revolution [백준 2342] - python

 

import sys
input = sys.stdin.readline
INF = 1e8

def BOJ2342() : 
  def get_distance(curr, target) :
    if curr == target :
      return 1
    elif curr == 0 :
      return 2 
    elif abs(curr - target) % 2 == 0 :
      return 4
    else : 
      return 3 

  l = list(map(int, input().split()))
  # dp[n 번째 움직임][왼발위치][오른발위치]
  dp = [[[INF for _ in range(5)] for _ in range(5)] for _ in range(len(l)+1)]
  dp[0][0][0] = 0

  for i in range(1, len(l)) :
    move = l[i-1]
    for left in range(5) :
      for right in range(5) :
        dp[i][move][right] = min(dp[i][move][right], dp[i-1][left][right] + get_distance(left, move))
        dp[i][left][move] = min(dp[i][left][move], dp[i-1][left][right] + get_distance(right, move))

  result = INF
  for i in range(5) :
    for j in range(5) :
      result = min(result, dp[len(l)-1][i][j])

  print(result)

BOJ2342()

 

접근 방법 :

1.  dp는 dp[n번째 움직임][왼발 위치][오른발 위치]

2. dp의 초기값은 매우 큰 값으로 세팅해 주었다. 문제에서 왼발을 움직이는 경우와 오른발을 움직이는 두 개의 경우가 있을 수 있으므로 이전의 어느 위치에서 오든지 두개의 경우를 모두 고려해 주어야 한다. 
* 만약 이동이 불가능 한 점에서 왼발 혹은 오른발을 옮겼을 경우 초기값이 무한대 값으로 설정되어 있으므로 움직였다 해도 무한대의 값으로 설정이 되어있을 것이다.

3. 마지막 index의 배열에서 최솟값을 구해주면 정답을 알 수 있다.

 

장애물 이였던 것 :

1. 결국 풀지 못했고 다른 분들의 풀이를 참고하였다.

 

 

 

 

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

2342번: Dance Dance Revolution