[그리디] 모두의 마블(12845)

문제 설명

 

영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다.

이번 이벤트는 다음과 같다. 순서가 매겨진 여러 장의 카드가 있다. 각각의 카드는 저마다 레벨이 있다.

카드 A에 카드 B를 덧붙일 수 있다. 이때 붙이는 조건은 다음과 같다.

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

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

영관이가 골드를 최대한 많이 받을 수 있게 여러분이 도와주자.

예를 들어, c1, c2, c3로 연속된 카드 3개가 있고 각각 레벨이 40,30,30 이라고 하자.

이 카드들을 합치는 과정에서, 먼저 c3에 c2를 합쳐 임시 카드 x1을 만든다. x1의 레벨은 30이고 획득 골드는 60이다. 그 다음엔 c1에 x1을 합쳐 카드 x2를 만들면 레벨이 40이고 70만큼의 골드를 획득할 수 있다. 이때, 영관이가 획득한 골드는 70+60 = 130이다.

다른 방법으로 c1에 c2를 덧붙인 카드 x1을 만들면, x1의 레벨은 40이고 획득한 골드는 70이다.

x1에 c3를 덧붙인 카드 x2의 레벨은 40이고 획득 골드는 70이다. 이때, 영관이가 획득한 골드는 70 + 70 = 140이다. 이외에 더 많은 골드를 받는 방법이 없으므로 140이 획득할 수 있는 최대 골드이다.

 

입력

카드의 개수 n(1 ≤ n ≤ 1,000)이 주어진다.

다음 줄에 각각 카드의 레벨 L𝚒가 순서대로 주어진다. (0 < L𝚒 ≤ 100,000)

 

출력

영관이가 받을 수 있는 골드의 최댓값을 출력한다.

 

---

🔍 문제 풀이

 

골드는 두 카드 레벨의 합으로 구해지므로 레벨의 최대값을 이용하는 방법으로 접근했다.

 

1.이중 탐색

 

① 주어진 (card 길이-1)만큼 두 카드의 레벨 합을 temp배열에 삽입한다. ➡︎ 결합 조건1을 만족하면서 카드 결합

② temp내 최댓값을 골드에 누적하고 해당 값의 인덱스를 찾는다.

③ ②에서 얻은 인덱스(card[index])와 바로 다음 인덱스(card[index+1]) 중 최댓값을 card에 추가한다. ➡︎ 결합 조건2를 만족하기 위함

④ 결합한 두 개의 카드(③의 두 카드)는 삭제한다.

⑤ card의 길이가 1이 될 때까지 ①~④ 반복한다.

 

결과는? 틀렸다🙅🏻‍♀️

과정이 복잡해서 코드를 작성할 때 실수했을 가능성이 있었기에 다른 방법을 고민했다🤔

 

2.정렬

 

① card 내림차순으로 정렬 ➡︎ card의 첫 번째 인덱스는 최댓값임

② 첫 번째와 두 번째 카드 레벨의 합을 골드에 누적 ➡︎ 결합 조건1을 만족하면서 카드 결합 

③ 두 카드 중 첫 번째 카드가 항상 최대이므로 card에 삽입 ➡︎ 결합 조건2를 만족하기 위함

④ 결합에 사용한 카드 삭제

⑤ card의 길이가 1이 될 때까지 ①~④ 반복한다.

 

import sys
input = sys.stdin.readline

n = int(input())
card = list(map(int, input().split()))
gold = 0

while len(card)>1: #5
  card.sort(reverse=True) #1: 내림차순 정렬
  gold+=(card[0]+card[1]) #2
  card.append(card[0]) #3
  del card[0:2] #4
  
print(gold)

결과는? 성공💪

시간 복잡도 ➠ O(n*n log n)으로 해결할 수 있었다.

 

---

📝 후기

 

첫 번째 로직은 주어진 테스트 케이스는 모두 통과했으나 실패했기에 코드 상 어느 부분에서 틀렸는지 쉽게 알지 못했다.

그래서 다른 로직을 생각해내면서 다행히도 맞출 수 있었다! 이래서 생각의 전환이 중요한 건가..😅

 

 

12845번: 모두의 마블