[백준][12845] 모두의 마블 | 파이썬 | 그리디(Greedy)

https://www.acmicpc.net/problem/12845

 

👉 문제 분석

순서가 매겨진 여러장의 카드가 있다.

각각의 카드는 저마다 레벨이 있다.

카드 합성을 할 때마다 두 카드 레벨의 합만큼 골드를 받는다.

카드 A에 B를 덧붙일 수 있다.

이 때 붙이는 조건:

1. 인접한 카드
2. 업그레이드 된 카드 A의 레벨은 변하지 않는다.

👉 알고리즘 설계

1. 카드의 개수 n개 입력받기
2. 카드 레벨 내림차순 정렬
3. cards[0]의 레벨 수에 계속 합쳐짐

👉 코드

import sys

n = int(input())
cards = list(map(int, sys.stdin.readline().split()))

cards.sort(reverse=True)  # 내림차순 정렬

gold = 0
for i in range(1, n):
    gold += (cards[0] + cards[i])
print(gold)

 

인접한 카드만 덧붙일 수 있으므로 내림차순으로 정렬한다.

어떤 카드를 인접하던 cards[0]에 합쳐야 최대 골드를 얻을 수 있다 (레벨수는 변하지 않으니). 

 

👉 시간복잡도

O(N)

 

👉 느낀점 or 기억할정보

문제를 풀기 전에 어떻게 접근하고 구현해 나갈지 더 구체적으로 고민해보고 pseudocode를 짜보자!