문제

숫자 타자 대회

풀이

  1. 숫자마다 for문을 돌면서 큐를 갱신함.
  2. 왼손이 움직이는 경우와, 오른손이 움직이는 경우를 따로 계산.
  3. 손의 위치가 같은 경우, 비용이 가장 작은 값만 저장.
  4. 마지막 큐에서 가장 작은 값 리턴.

처음에는 다익스트라로 시도를 했는데, 시간 초과가 났다. 좀 더 고민해보면 이 문제는 그리디로 해결 가능하다. 근데 그리디로 코드를 바꿔도 시간 초과가 났다. move 함수 부분을 원래는 그래프 탐색으로 구현했는데, 간단하게 하드코딩이 가능했다. (x값 차이 + y값 차이)에 움직인 횟수를 더해주면 되는데, 움직인 횟수는 x값 차이와 y값의 차이의 최대값으로 쉽게 구할 수 있다. 제자리에 있는 경우에는 1을 더해주면 된다.

풀이 코드

def solution(numbers):
    n = len(numbers)
    g = [[1,3],[0,0],[1,0],[2,0],[0,1],[1,1],[2,1],[0,2],[1,2],[2,2]]
    dp = [[0 for _ in range(10)] for _ in range(n)]
    q = [(0, 0, 4, 6)]

    def move(s, w, e):
        sx, sy = g[s]
        ex, ey = g[e]
        if e==w: return 0
        return abs(sx-ex)+abs(sy-ey) + max(abs(sx-ex), abs(sy-ey), 1)
    
    ans = 10**8
    q1, q2 = [[0, 4, 6]], []
    for n in numbers:
        n = int(n)
        for t, lh, rh in q1:
            dt = move(lh, rh, n)
            if dt:
                for i, q in enumerate(q2):
                    if (q[1] == n and q[2] == rh) or (q[1] == rh and q[2] == n):
                        q2[i][0] = min(q2[i][0], t+dt)
                        break
                else: q2.append([t+dt, n, rh])

            dt = move(rh, lh, n)
            if dt:
                for i, q in enumerate(q2):
                    if (q[1] == n and q[2] == lh) or (q[1] == lh and q[2] == n):
                        q2[i][0] = min(q2[i][0], t+dt)
                        break
                else: q2.append([t+dt, lh, n])
        q1, q2 = q2, []
    for q in q1: ans = min(ans, q[0])
    return ans