12845 모두의 마블

💡문제 분석 요약

• 카드 합성시 합쳐진 카드의 레벨만큼 돈을 받고, 이 돈이 최대가 되는 경우를 구한다.
• 레벨이 높은 카드는 합쳐져도 레벨이 변하지 않는다. = 즉, 계속 사용된다

💡알고리즘 설계

• 인덱스를 신경써야하는 것으로 이해해서, enumerate나 dictionary를 생각했다. 근데 enumerate는 인덱스 값을 변경할 수가 없었다.
• 그러나 카드의 위치가 고정이 아니라는 것을 알고, 정렬 후 최대 레벨의 카드를 기준으로 합치면 된다고 생각했다.

💡코드

n = int(input())
cards = sorted(list(map(int, input().split())))
print(cards[-1]*(n-1) + sum(cards[:n-1]))

"""
1. 일단 정렬해서 가장 큰 레벨을 뒤로 빼줌. (최대 레벨이 기준이 됨)
2. 예시를 보면 알겠지만, 가장 큰 레벨은 계속해서 쌓이는 형식임.
ex) 40+30 , 40+30 , .... 즉 가장 큰 레벨은 n-1번 계속해서 더해짐.
3. 그럼 나머지 값들은 큰 값에 단순히 더해지는 것이니, 이를 따로 더해서 나중에 합치는 것과 같음.
ex) 10 20 30 40 이렇게 있다고 하면 합치는 순서는 40+30 + 40+20 + 40+10 이므로 40*(4-1) + sum(10,20,30)과 같음.
"""

💡시간복잡도

• sort에서 O(N log N)만큼 소요된다.

💡 틀린 이유

• 카드가 고정된 상태라고 생각했어서, 인덱스를 조정해야하나 싶었는데 그게 아니라서 정렬로 쉽게 해결할 수 있었다.

💡 틀린 부분 수정 or 다른 풀이

• 카드를 정렬하고, 최대 레벨을 기준으로 최대 gold를 구한다.

💡 느낀점 or 기억할정보

• 항상 문제 이해를 정말 잘해야한다는 생각이 든다. 10분정도는 문제를 쭉 읽으며 이해하는 시간을 가지고, 30분정도는 코딩하는 시간으로 가져야겠다.