백준 2342 Dance Dance Revolution

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/2342

풀이

난이도 : Gold III

이 문제를 처음 풀 때는 greedy로 모든 곳을 탐색하면서 q에 경우의 수를 늘려가면서 해결하려고 하였다.
그렇게 풀었을 경우에 예외 처리를 많이 해주어야 되고, step은 똑같은데 값만 다른 것들이 중복되는 것을 확인하였으며, 결론적으로 시간 초과가 났다.

그래서 dp를 이용하여 풀게 되었고, 3중 array로 dp를 구성하여 bottom up 형식으로 풀었다.

instruction의 최대 개수가 100000이므로, instruction 하나당 1번,2번,3번,4번칸과 왼발, 오른발의 모든 경우의 수를 생각해보아도 시간초과없이 해결할 수 있을 것이라 생각하였다.

• dp[a][b][c]
  • a는 instruction index를 가리킨다.
  • b는 left 위치를 가리킨다.
  • c는 right 위치를 가리킨다.

1) instruction의 마지막은 0이 입력되므로 n 을 len(ins) - 1 로 구성하여 0은 참조하지 않도록 해준다.
2) move라는 함수는 문제에 구현되어 있는 이동할 때 드는 힘을 그대로 구현한다.
3) 모든 instruction에 대하여 bottom up으로 dp를 채워나간다.

👉 현재 채워져있는 dp상태와 전 단계(i-1)에서 이곳으로 이동해왔을 때 값을 비교하여 작은 값으로 dp 값을 다시 정해준다.
(처음 상태에서 i-1로 참조했을 때를 대비해 시작 전에 dp[-1][0][0] = 0 으로 조치를 해두었음)

코드

ins = list(map(int, input().split()))
n = len(ins)-1
dp = [[[400001 for _ in range(5)] for _ in range(5)] for _ in range(n+1)]
dp[-1][0][0] = 0

def move(start, end):
    if start == 0:
        if end == 0:
            return 0
        else:
            return 2

    if start == end:
        return 1
    elif abs(start - end) == 1 or abs(start - end) == 3:
        return 3
    else:
        return 4

for i in range(n):
    for current in range(5):
        for start in range(5):
            add = move(start, ins[i])
            # 왼발 이동
            dp[i][ins[i]][current] = min(dp[i][ins[i]][current], dp[i-1][start][current] + add)
            # 오른발 이동
            dp[i][current][ins[i]] = min(dp[i][current][ins[i]], dp[i-1][current][start] + add)

result = int(1e9)
for l in range(5):
    for r in range(5):
        result = min(result, dp[n-1][l][r])
print(result)