[Python] 백준(BOJ): 12845 모두의 마블

문제

12845번: 모두의 마블

---

풀이

레벨이 제일 큰 카드를 기준으로 골드의 값을 업데이트해나가면 되는 greedy 문제이다.

a. 풀이

1) 가장 레벨값이 큰 카드를 찾는다
2) 1)에서 얻은 카드의 (왼쪽,오른쪽) 카드 중 레벨값이 더 작은 것을 먼저 흡수한다
3) 골드값을 업데이트하고, 흡수한 카드를 list에서 제거한다
4) 카드가 1개만 남을 때까지 1)~3)을 반복 수행한다

n = int(input())
data = [i for i in map(int, input().split())]

answer = 0

while len(data) > 1:
    # 최대의 레벨값을 가지는 card를 선택
    card = max(data)
    idx = data.index(card)

    left = data[idx - 1] if idx > 0 else 100001
    right = data[idx + 1] if idx < len(data) - 1 else 100001

    # 왼쪽과 오른쪽 중 더 작은 레벨값을 카지는 카드를 선택하여 흡수
    if left < right:
        new_card_value = left
        new_card_idx = idx - 1
    else:
        new_card_value = right
        new_card_idx = idx + 1

    # goal값을 갱신하고, 흡수할 카드를 data에서 제거
    answer += new_card_value + card
    data.remove(new_card_value)

print(answer)