Dance Dance Revolution

• 기초적인 DP 문제
• DP[n][(x,y)] 를 두 발의 위치가 x와 y인 상태로 n번째지시사항까지 처리했을때의 최소 힘이라고 정의하고, energy(a, b)를 a에 있던 발을 b로 옮길때 드는 힘이라고 정의하자. n번째 지시사항이 x였다면 점화식은 다음의 형태로 나온다
  • DP[n][(x,y)] = min_z{DP[n-1][(z,y)]+energy(z,x)}
  • 불가능한 포지션, x가 포함되지 않은 포지션 또는 두 발이 같은 위치에 있는 포지션들은 DP값을 전부 INF로 만들어주면 된다.
• 그러나 n번째 지시사항이 끝난 뒤에는 한 발은 항상 특정 위치에 가있어야 하기 때문에, 이렇게 모든(x,y)에 대해서 테이블을 유지하는 것은 조금 비효율적이다. DP테이블을 조금 수정해서, DP[n][y] 를 한발의 위치는 n번째 지시위치에, 다른 발의 위치는 y에 가있는 경우의 최소 힘으로 정의해보자. n번째 지시위치를 cmd[n]이라고 하면, n-1번째에서 발이 cmd[n-1]과 x에 있었으므로, n번째에는 x에 있던 발로 cmd[n]을 누르는 경우와 cmd[n-1]에 있던 발로 cmd[n]을 누르는 두가지로 나눠서 생각할수 있다. 즉 점화식은 아래처럼 나온다
  • DP[n][x] = min{DP[n-1][x]+energy(cmd[n-1],cmd[n]), DP[n-1][cmd[n]]+energy(cmd[n-1],x)}
• 위의 방식에 비해서 메모리와 속도 모두 조금 더 효율적이다.
• 어떤 방식으로 DP식을 정의하든, 포지션의 갯수는 고정되어 있으므로 상수라고 놓으면 시간복잡도는 O(n)이다. (n=지시사항의 갯수)

"""Solution code for "BOJ 2342. Dance Dance Revolution".

- Problem link: https://www.acmicpc.net/problem/2342
- Solution link: http://www.teferi.net/ps/problems/boj/2342

Tags: [DP]
"""

INF = float('inf')


def energy(cur_pos, next_pos):
    if cur_pos == next_pos:
        return 1
    if cur_pos == 0:
        return 2
    elif abs(cur_pos - next_pos) == 2:
        return 4
    else:
        return 3


def main():
    positions = [int(x) for x in input().split()]
    positions.pop()
    dp_cur = [INF] * 5
    dp_cur[0] = energy(0, positions[0])
    for prev_pos, cur_pos in zip(positions, positions[1:]):
        dp_prev = dp_cur
        # (prev_pos, pprev_pos) -> (cur_pos, pprev_pos)
        energy_from_prev = energy(prev_pos, cur_pos)
        dp_cur = [tot_energy + energy_from_prev for tot_energy in dp_prev]
        dp_cur[cur_pos] = INF
        # (prev_pos, pprev_pos) -> (prev_pos, cur_pos)
        if prev_pos != cur_pos:
            dp_cur[prev_pos] = min(
                tot_energy + energy(pprev_pos, cur_pos)
                for pprev_pos, tot_energy in enumerate(dp_prev))

    print(min(dp_cur))


if __name__ == '__main__':
    main()