사칙연산

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

DP 대신 재귀와 lru_cache로 풀 수 있을 때도 있다~!

from functools import lru_cache


def solution(arr):
    @lru_cache(maxsize=None)
    def solve(t):
        if len(t) == 1:
            return [int(t[0])]
        result = [n1 + (n2 if t[i] == "+" else -n2)
                  for i in range(1, len(t), 2)
                  for n1 in solve(t[:i])
                  for n2 in solve(t[(i + 1):])]
        return [max(result), min(result)]

    return max(solve(tuple(arr)))

정확성  테스트
테스트 1 〉	통과 (0.31ms, 10.4MB)
테스트 2 〉	통과 (0.32ms, 10.3MB)
테스트 3 〉	통과 (0.47ms, 10.4MB)
테스트 4 〉	통과 (0.31ms, 10.5MB)
테스트 5 〉	통과 (0.49ms, 10.2MB)
테스트 6 〉	통과 (0.30ms, 10.2MB)
테스트 7 〉	통과 (0.52ms, 10.2MB)
테스트 8 〉	통과 (0.30ms, 10.5MB)
테스트 9 〉	통과 (0.08ms, 10.5MB)
테스트 10 〉	통과 (0.03ms, 10.3MB)
효율성  테스트
테스트 1 〉	통과 (401.04ms, 14.4MB)
테스트 2 〉	통과 (421.63ms, 14.5MB)
테스트 3 〉	통과 (426.63ms, 14.5MB)
테스트 4 〉	통과 (30.50ms, 10.6MB)
테스트 5 〉	통과 (414.69ms, 14.3MB)
테스트 6 〉	통과 (383.95ms, 14.3MB)
테스트 7 〉	통과 (389.50ms, 14.4MB)
테스트 8 〉	통과 (418.97ms, 14.5MB)