백준 12845(Python) 풀이 : 모두의 마블

백준 12845 문제

백준 링크 : https://www.acmicpc.net/problem/12845

백준 12845 풀이

이 문제에서, 두 카드를 합치게 되면 더 레벨이 큰 카드로 남게 된다. 그리고 레벨은 카드를 더하는 과정에서 골드로 바뀌기 때문에 가능한 레벨을 높게, 그리고 많이 카드를 만들어야 한다.

결국 그러기 위해서는 카드 중에서 가장 레벨이 높은 카드를 찾아서, 그 카드와 나머지 카드를 전부 합쳐나가면 된다.

예를 들어, 50 40 30 20 10 이라는 카드 3장이 있다고 쳐 보자. 이때 최대값은,

(50+40) + (50+30) + (50+20) + (50+10) 이렇게 된다. 그런데, 이 식은 결국 최대값 * (n-1) + 나머지 모든 항의 합으로 요약될 수 있다. 이것도 또 바꿔 말하면, 모든 항의 합 + 최대값*(n-2)인 것이다.

# 입력
n = int(input())
lvs = list(map(int, input().split()))

# 최대값
max_lv = max(lvs)

# 골드 최대값 : 최대값*(n-2) + 전체의 합
sum_lv = max_lv * (n - 2) + sum(lvs)

# 출력
print(sum_lv)