1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
def solution(numbers):

    def dfs(idx, L, R, cost):

        if idx == len(numbers): #end
            return

        GOAL = int(numbers[idx])
        L_COST = weight(L, GOAL)
        R_COST = weight(R, GOAL)

        #recursive
        if R != GOAL:
            if cost + L_COST < dp[idx][GOAL][R]: #left
                dp[idx][GOAL][R] = cost + L_COST
                dfs(idx+1, GOAL, R, cost + L_COST)

        if L != GOAL:
            if cost + R_COST < dp[idx][L][GOAL]: #right
                dp[idx][L][GOAL] = cost + R_COST
                dfs(idx+1, L, GOAL, cost + R_COST)

    def weight(start, end):
        start = pad[start]
        end = pad[end]
        diff = [abs(end[0]-start[0]), abs(end[1]-start[1])]
        common = min(diff)
        other = max(diff)
        return max(common * 3 + ((other - common) * 2), 1)

    answer = 987654321
    pad = {0: (4, 2)}
    INF = 987654321
    L = 4
    R = 6

    for i in range(1, 4):
        for j in range(1, 4):
            pad[j + ((i-1) * 3)] = (i, j)

    dp = [[[INF for i in range(10)] for j in range(10)] for k in range(len(numbers))]

    dfs(0, L, R, 0)

    for i in range(10):
        for j in range(10):
            answer = min(answer, dp[len(numbers)-1][i][j])

    return answer