카운트 다운

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

def solution(target):
    import sys
    import heapq

    def dp(rest_score):
        if rest_score == 0:
            return 0, 0
        if memo[rest_score]:
            return memo[rest_score]
        heap = []
        for score in scores:
            if score == 50 and (next_score := rest_score - 50) >= 0:
                temp = dp(next_score)
                heapq.heappush(heap, (temp[0] + 1, temp[1] - 1))
                continue
            if (next_score := rest_score - score) >= 0:
                temp = dp(next_score)
                heapq.heappush(heap, (temp[0] + 1, temp[1] - 1))
            if (next_score := rest_score - score * 2) >= 0:
                temp = dp(next_score)
                heapq.heappush(heap, (temp[0] + 1, temp[1]))
            if (next_score := rest_score - score * 3) >= 0:
                temp = dp(next_score)
                heapq.heappush(heap, (temp[0] + 1, temp[1]))
        memo[rest_score] = heapq.heappop(heap)
        return memo[rest_score]

    sys.setrecursionlimit(300000)
    scores = [50] + list(range(1, 21))
    memo = [[] for _ in range(target + 2)]
    result = dp(target)
    return [result[0], -result[1]]

테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (2280.27ms, 19.8MB)
테스트 3 〉	통과 (1608.14ms, 16.9MB)
테스트 4 〉	통과 (1691.25ms, 17.2MB)
테스트 5 〉	통과 (1899.00ms, 18.4MB)
테스트 6 〉	통과 (2099.21ms, 17.8MB)
테스트 7 〉	통과 (1830.62ms, 17.8MB)
테스트 8 〉	통과 (117.84ms, 10.6MB)
테스트 9 〉	통과 (1979.55ms, 18.4MB)
테스트 10 〉	통과 (270.03ms, 11.1MB)
테스트 11 〉	통과 (394.61ms, 11.4MB)
테스트 12 〉	통과 (2278.36ms, 18.9MB)
테스트 13 〉	통과 (588.65ms, 12.2MB)
테스트 14 〉	통과 (2393.16ms, 19.6MB)
테스트 15 〉	통과 (1806.70ms, 16.9MB)
테스트 16 〉	통과 (384.51ms, 11.5MB)
테스트 17 〉	통과 (237.23ms, 10.7MB)
테스트 18 〉	통과 (2302.74ms, 19.1MB)
테스트 19 〉	통과 (1044.80ms, 14MB)
테스트 20 〉	통과 (2544.40ms, 20.7MB)
테스트 21 〉	통과 (0.66ms, 10.3MB)
테스트 22 〉	통과 (0.56ms, 10.2MB)
테스트 23 〉	통과 (0.76ms, 10.2MB)
테스트 24 〉	통과 (0.67ms, 10.1MB)
테스트 25 〉	통과 (0.42ms, 10.3MB)