백준 11399 ATM

✅ 백준 11399 ATM

정답.

동적 계획법으로 풀었다.

특별한 점이라면 제일 큰 숫자가 마지막으로 가야 최솟값이 된다.

그것 외에는 어제랑 그저께 풀었던 동적 계획법 문제랑 똑같다.

import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())

num_arr = list(map(int,sys.stdin.readline().rstrip().split()))

cache = [-1] * n
result = 0

num_arr.sort()
def p(idx) :
    global result
    if idx == 0 :
        result += num_arr[0]
        return num_arr[0]
    if cache[idx] != -1 :
        return cache[idx]
    val = num_arr[idx] + p(idx-1)
    cache[idx] = val
    result += val
    return val

p(n-1)
print(result)