그리디(Greedy) 알고리즘 백준#12845 #실버 | "모두의 마블" | 파이썬 풀이

문제

문제 원본: https://www.acmicpc.net/problem/12845

12845번: 모두의 마블

접근법

가장 높은 골드를 획득하는 방법, 간단합니다.

레벨이 가장 높은 카드 1장을 고정하고 나머지 카드와 차례로 덧셈하면 됩니다.

어차피 모든 카드의 레벨과 합산해야 하며,

두 카드의 덧셈이(=획득 골드량) 최대가 되기 위해서는 최상위 레벨의 카드 1장을 고정시키면 되는 것이죠.

소스코드

# 카드 개수 입력받기
n = int(input())

# 카드별 레벨 입력받기
level_list = list(map(int, input().split()))
# 카드 레별에 따라 내림차순 정렬
level_list.sort(reverse= True)
# 획득할 골드 초기화
answer = 0
# 가장 큰 레벨 카드 2장 합산
answer += level_list[0] + level_list[1]

# 레벨 큰 순서대로 카드 합산
for i in range(2, n):
    answer +=level_list[0] + level_list[i]

print(answer)

레벨에 따라 카드를 내림차순으로 정렬했기 때문에 최상위 레벨의 카드는 [0] 인덱스 요소입니다.

해당 원소를 고정하고 나머지 카드와 한 번씩 더해 나가면 정답이 됩니다.

시간 복잡도: O(N)

하나의 카드는 고정되고 나머지 카드 1장씩 더해지는 연산을 총 (N-1)번 반복하므로 시간 복잡도는 O(N)입니다.

---

더 좋은 아이디어가 있으시거나 포스팅 내용에 오류가 있다면 아래에 👇👇👇 댓글 남겨주세요!

그럼 오늘도 건강하고 즐거운 하루 보내시길 바랍니다 :-)

고맙습니다.