[백준] 모두의 마블 : 12845번 - Python

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

12845번: 모두의 마블

 

 

 

문제의 접근 방법

 

- 카드를 합치는 과정에 대해 그림을 그려서 표현해보기

- 가장 처음에 카드를 합칠 때 레벨이 제일 높은 카드에 합쳐야 골드의 값이 최대가 될 수 있음.

 

다음과 같은 레벨을 가진 카드 C1,C2,C3 3장이 있다.

 

 

문제에서 말한 예시를 그림으로 표현해 봄.

 

 

---> 2번과 같은 방식으로 카드를 합쳐야 최대 골드를 획득할 수 있다!

그림을 그려놓고 보니 1번과 2번의 가장 큰 차이점이 처음에 합친 카드의 레벨이라는 것을 알 수 있었다. 합성할 수 있는 두 카드 A,B는 늘 인접해야 하고 A의 레벨이 변하지 않기 때문에 처음 선택되는 카드 A의 레벨이 가장 커야한다.

 

 

 

문제 풀이 방법

 

(1) 카드의 개수 n개 입력받기

(2) n개의 카드의 레벨을 입력받아 리스트 level에 저장하기

(3) 위에서 설명했던 이유로 리스트 level을 내림차순 정렬하기

(4) 늘 제일 첫 번째 값(계속 가장 큰 값에 합성해야 최댓값을 구할 수 있기 때문)을 계산하기 위해 반복문 안에서 i는 계속 0으로 초기화 시켜주기

(5) 미리 선언해 둔 변수 gold에 인접한 카드를 합성해 얻은 골드(각 레벨끼리 더한 값)를 누적해서 더해주기

(6) (5)에서 합성한 카드는 이미 레벨이 더 큰 카드에 합성되어서 더 이상 존재하지 않기 때문에 삭제 해주기

(7) (4)~(6)의 과정을 카드가 다 합성될 때까지 반복하기

(8) 누적해서 더해진 최댓값 gold 출력하기!

 

 

 

소스코드

n = int(input())

level = list(map(int, input().split()))
level.sort(reverse=True)

gold = 0
for i in range(len(level)-1):
    i = 0
    gold += level[i] + level[i+1]
    del level[i+1]

print(gold)