[C++] 백준 12845번 모두의 마블

1. 문제이해

12845번: 모두의 마블 (acmicpc.net)

12845번: 모두의 마블

 

 

영관이는 N장의 카드들 중 인접한 카드 2장을 골라, 카드를 합성하려고 한다.

카드를 합성할 때마다, 두 카드의 레벨의 합 만큼 골드를 얻고, 업그레이드 된 카드의 레벨을 변하지 않는다.

이때, 영광이가 벌 수 있는 최대 골드는 얼마인지를 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

N장의 카드 중 인접한 카드 2장을 골라 합성해나가며,

합성한 카드의 레벨의 합만큼 골드를 얻는 방식이다.

위의 문제를 제대로 이해하기 위해, 두 가지 예제를 살펴보자.

(첫번째 예제는 문제의 예제와 동일하다.)

 

<예제 1>

40 , 30 , 30

인 세 장의 카드가 주어졌을 때, 앞에서 부터 합성하면,

 

1. (40, 30) 합성

골드 : 40 + 30 = 70

남은 카드 : 40 , 30

 

2. (40, 30) 합성

골드 : (40 + 30) + 40 + 30 = 140

남은 카드 : 40 (한장이므로 종료)

 

최대 총 140원의 골드를 받을 수 있게 된다.

왜 앞에서부터 합성해야 하는지는 아래 예제 2에서 자세히 보자.😤

 

<예제 2>

20 , 30 , 40 , 50 , 30

인 다섯장의 카드가 주어졌을 때, 우선 내림차순으로 다시 정렬해보자.

50 , 40 , 30 , 30 , 20

이 순서대로 합성을 시작하면,

 

1. (50, 40) 합성

골드 : 50 + 40 = 90

남은 카드 : 50 , 30 , 30 , 20

 

2. (50, 30) 합성

골드 : (50 + 40) + 50 + 30 = 170

남은 카드 : 50 , 30 , 20

 

3. (50, 30) 합성

골드 : (50 + 40 + 50 + 30) + 50 + 30 = 250

남은 카드 : 50 , 20

 

4. (50, 20) 합성

골드 : (50 + 40 + 50 + 30 + 50 + 30) + (50 + 20) = 320

남은 카드 : 50 (한장이므로 종료)

 

위의 과정을 보면 어떤 규칙이 눈에 보일것이다.

바로, 첫번째 짝을 지은 두 카드 중 레벨이 큰 카드가 계속해서 더해진다는 점이다.

(이 예제에서는 50에 해당한다.)

 

내림차순으로 굳이 정의한 이유는 위와 같은 이유때문이다.

골드의 총합이 최대가 되려면, 첫번째로 묶인 두 카드 중 큰 값은 계속해서 더해지기 때문에,

이 값이 클 수록 받는 골드도 커질 것이다.

따라서, 내림차순으로 정의 후 레벨이 가장 큰 값부터 차례로 합성해나가는 것이 이득이 된다.

 

또한, 첫번째 짝을 지은 카드 중 레벨이 큰 카드가 계속해서 더해진다는 점에 다시 주목해보자.

골드 현황을 계속해서 살펴보면, 이전 골드에서 계속되는 값인 50을 제외하고는,

나머지 값들을 계속해서 더해주는 꼴이 나타난다.

즉, 다음과 같은 꼴이 계속해서 나타난다.

골드  = (이전 골드의 총합) + 레벨이 가장 큰 값 + 내림차순 순서대로의 값

( 여기서 내림차순 순서대로의 값은, 50 40 30 30 20 이므로,

한단계씩 진행될때마다 저 순서대로의 값이 더해진다는 이야기이다. (50은 제외) )

 

즉, 이 문제의 핵심은 다음과 같다.

1. 내림차순으로 정의할 것

2. 골드  = (이전 골드의 총합) + 레벨이 가장 큰 값 + 내림차순 순서대로의 값

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>
using namespace std;

// 내림차순
bool DESC(int a, int b) {
	return a > b;
}

int main() {
	int N;	// 카드의 개수
	int level[1000];	// 카드의 레벨
	int gold = 0;	// 골드

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> level[i];
	}

	// 내림차순으로 정렬
	sort(level, level + N, DESC);

	for (int i = 1; i < N; i++) {
		// 가장 큰 값은 계속 더해지므로,
		// 가장 큰 값+ 나머지 값들을 계속 더해나감
		gold += (level[0] + level[i]);
	}

	cout << gold;

	return 0;
}

장황한 설명에 비해 코드는 비교적 간단하다.

간단하게 코드를 만들기까지 생각하는 과정이 조금 힘들 뿐...😰

 

먼저 카드의 개수(N)와 각 카드의 레벨(level[i])을 입력받는다.

이후 각 카드의 레벨을 내림차순으로 정렬한 후,

위에서 이야기 했듯, 골드  = (이전 골드의 총합) + 레벨이 가장 큰 값 + 내림차순 순서대로의 값이므로,

gold += (level[0] + level[i]); 로 나타내주었다.

(여기서 level[0]은 레벨이 가장 높은 값. 계속 더해져나가는 값.

level[i]는 최대값인 level[0]을 제외한 다른 값들. 내림차순 순서대로의 값들이다.)

 

 

---

항상 예제를 들어 설명하는 것이 가장 이해가 빨리 되는 것 같다.

이래저래 원리만 설명하고 넘어가도 하나도 이해가 안되고...😥

예제를 하나하나 써가며 풀어봤더니

역시 왜 이런 알고리즘이 나오는지 이해가 되더라😊

오늘도 장황하게 설명을 해봤는데, 조금 더 가독성있게 글을 쓸수 있도록 노력해야겠다.💪