숫자 타자 대회

https://school.programmers.co.kr/learn/courses/30/lessons/136797

간단히 완전 탐색. 당연히 시간 제한. 문제는 제대로 이해한 것 같고.. 

def solution(numbers):
    def search(left, right, index, total):
        if len(numbers) == index:
            return total
        if left == right:
            return float('inf')
        number = int(numbers[index])
        left_total = search(number, right, index + 1, total) + weights[left][number]
        right_total = search(left, number, index + 1, total) + weights[right][number]
        return min(left_total, right_total)

    import sys
    sys.setrecursionlimit(300_000)
    weights = ((1, 7, 6, 7, 5, 4, 5, 3, 2, 3),
               (7, 1, 2, 4, 2, 3, 5, 4, 5, 6),
               (6, 2, 1, 2, 3, 2, 3, 5, 4, 5),
               (7, 4, 2, 1, 5, 3, 2, 6, 5, 4),
               (5, 2, 3, 5, 1, 2, 4, 2, 3, 5),
               (4, 3, 2, 3, 2, 1, 2, 3, 2, 3),
               (5, 5, 3, 2, 4, 2, 1, 5, 3, 2),
               (3, 4, 5, 6, 2, 3, 5, 1, 2, 4),
               (2, 5, 4, 5, 3, 2, 3, 2, 1, 2),
               (3, 6, 5, 4, 5, 3, 2, 4, 2, 1))
    return search(4, 6, 0, 0)

테스트 1 〉	통과 (0.02ms, 10.5MB)
테스트 2 〉	통과 (0.02ms, 10.5MB)
테스트 3 〉	통과 (0.03ms, 10.3MB)
테스트 4 〉	통과 (0.03ms, 10.6MB)
테스트 5 〉	통과 (0.03ms, 10.6MB)
테스트 6 〉	통과 (0.07ms, 10.5MB)
테스트 7 〉	통과 (0.06ms, 10.4MB)
테스트 8 〉	통과 (0.05ms, 10.3MB)
테스트 9 〉	통과 (0.05ms, 10.4MB)
테스트 10 〉	통과 (0.04ms, 10.4MB)
테스트 11 〉	통과 (110.54ms, 10.4MB)
테스트 12 〉	통과 (35.53ms, 10.3MB)
테스트 13 〉	통과 (57.91ms, 10.4MB)
테스트 14 〉	통과 (18.77ms, 10.4MB)
테스트 15 〉	통과 (28.94ms, 10.4MB)
테스트 16 〉	실패 (시간 초과)
테스트 17 〉	실패 (시간 초과)
테스트 18 〉	실패 (시간 초과)
테스트 19 〉	실패 (시간 초과)
테스트 20 〉	실패 (시간 초과)

lru_cache를 이용해 보자. 
lru_cache는 함수의 결과를 캐싱해준다. (메모이제이션과 비슷하다.)
간단하게 데코레이터 하나로 재귀함수를 (유사) 동적계획법으로 바꿔준다.
엄청난 파이썬... 

import sys
from functools import lru_cache


def solution(numbers):
    @lru_cache(maxsize=None)
    def search(left, right, index, total):
        if len(numbers) == index:
            return total
        if left == right:
            return float('inf')
        number = int(numbers[index])
        left_total = search(number, right, index + 1, total) + weights[left][number]
        right_total = search(left, number, index + 1, total) + weights[right][number]
        return min(left_total, right_total)

    sys.setrecursionlimit(300_000)
    weights = ((1, 7, 6, 7, 5, 4, 5, 3, 2, 3),
               (7, 1, 2, 4, 2, 3, 5, 4, 5, 6),
               (6, 2, 1, 2, 3, 2, 3, 5, 4, 5),
               (7, 4, 2, 1, 5, 3, 2, 6, 5, 4),
               (5, 2, 3, 5, 1, 2, 4, 2, 3, 5),
               (4, 3, 2, 3, 2, 1, 2, 3, 2, 3),
               (5, 5, 3, 2, 4, 2, 1, 5, 3, 2),
               (3, 4, 5, 6, 2, 3, 5, 1, 2, 4),
               (2, 5, 4, 5, 3, 2, 3, 2, 1, 2),
               (3, 6, 5, 4, 5, 3, 2, 4, 2, 1))
    return search(4, 6, 0, 0)

테스트 1 〉	통과 (0.04ms, 10.3MB)
테스트 2 〉	통과 (0.03ms, 10.6MB)
테스트 3 〉	통과 (0.04ms, 10.2MB)
테스트 4 〉	통과 (0.04ms, 10.4MB)
테스트 5 〉	통과 (0.05ms, 10.2MB)
테스트 6 〉	통과 (0.05ms, 10.6MB)
테스트 7 〉	통과 (0.07ms, 10.4MB)
테스트 8 〉	통과 (0.06ms, 10.3MB)
테스트 9 〉	통과 (0.05ms, 10.3MB)
테스트 10 〉	통과 (0.07ms, 10.4MB)
테스트 11 〉	통과 (0.34ms, 10.4MB)
테스트 12 〉	통과 (0.33ms, 10.2MB)
테스트 13 〉	통과 (0.32ms, 10.2MB)
테스트 14 〉	통과 (0.31ms, 10.4MB)
테스트 15 〉	통과 (0.15ms, 10.4MB)
테스트 16 〉	통과 (500.07ms, 109MB)
테스트 17 〉	통과 (753.65ms, 151MB)
테스트 18 〉	통과 (1199.21ms, 230MB)
테스트 19 〉	통과 (1618.83ms, 306MB)
테스트 20 〉	통과 (2571.25ms, 442MB)

너비 우선 탐색(BFS)와 DP로... 

def solution(numbers):
    weights = ((1, 7, 6, 7, 5, 4, 5, 3, 2, 3),
               (7, 1, 2, 4, 2, 3, 5, 4, 5, 6),
               (6, 2, 1, 2, 3, 2, 3, 5, 4, 5),
               (7, 4, 2, 1, 5, 3, 2, 6, 5, 4),
               (5, 2, 3, 5, 1, 2, 4, 2, 3, 5),
               (4, 3, 2, 3, 2, 1, 2, 3, 2, 3),
               (5, 5, 3, 2, 4, 2, 1, 5, 3, 2),
               (3, 4, 5, 6, 2, 3, 5, 1, 2, 4),
               (2, 5, 4, 5, 3, 2, 3, 2, 1, 2),
               (3, 6, 5, 4, 5, 3, 2, 4, 2, 1))
    dp = {(4, 6): 0, (6, 4): 0}
    for number in numbers:
        number = int(number)
        new_dp = {}
        for (idx1, idx2), total in dp.items():
            if idx1 == number or idx2 == number:
                result = min(new_dp.get((idx1, idx2), float('inf')), total + 1)
                new_dp[(idx1, idx2)] = result
                new_dp[(idx2, idx1)] = result
            else:
                result1 = min(new_dp.get((idx1, number), float('inf')), total + weights[idx2][number])
                result2 = min(new_dp.get((idx2, number), float('inf')), total + weights[idx1][number])
                new_dp[(idx1, number)] = result1
                new_dp[(number, idx1)] = result1
                new_dp[(idx2, number)] = result2
                new_dp[(number, idx2)] = result2
        dp = new_dp
    return min(dp.values())

테스트 1 〉	통과 (0.02ms, 10.4MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.02ms, 10.4MB)
테스트 4 〉	통과 (0.03ms, 10.2MB)
테스트 5 〉	통과 (0.05ms, 10.4MB)
테스트 6 〉	통과 (0.06ms, 10.2MB)
테스트 7 〉	통과 (0.05ms, 10.4MB)
테스트 8 〉	통과 (0.06ms, 10.3MB)
테스트 9 〉	통과 (0.05ms, 10.4MB)
테스트 10 〉	통과 (0.05ms, 10.2MB)
테스트 11 〉	통과 (0.44ms, 10.2MB)
테스트 12 〉	통과 (0.25ms, 10.2MB)
테스트 13 〉	통과 (0.24ms, 10.3MB)
테스트 14 〉	통과 (0.44ms, 10.4MB)
테스트 15 〉	통과 (0.27ms, 10.4MB)
테스트 16 〉	통과 (456.63ms, 10.3MB)
테스트 17 〉	통과 (760.18ms, 10.5MB)
테스트 18 〉	통과 (1171.43ms, 10.6MB)
테스트 19 〉	통과 (1519.23ms, 10.5MB)
테스트 20 〉	통과 (2281.02ms, 10.4MB)