백준 12845번 : 모두의 마블 C++

 

 

처음에 어떻게 풀까 고민을 많이 했다.

그리디 알고리즘 문제이니 가장 높은 레벨을 찾은 후에 양쪽을 확인하고 더하면서 문제를 풀면 되겠다 라고 생각했다.

 

어쨋든 처음부터 가장큰 레벨인 것부터 시작하는 것이 가장 큰값이 나올것이기 때문..

근데 이걸 생각하다보니 의문이 들었다.

 

이런식의 연산을 하다보면 가장 큰레벨의 값은 처음 부터 끝까지 모든 덧셈에 포함된다. 정확히 n-1번의 덧셈에 포함이 된다. 그리고 나머지 레벨들은 한번씩 더해진다. 

그럼 결과는 아주 쉽게 도출될 수 있었다. 

 

(가장 큰 레벨) * (n-1) + (나머지 레벨들의 합)

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

int n, maxgold;
const int MAX = 1000001;
int arr[MAX];

int main(void) {

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

	int maxlevel = arr[0];
	int sum = 0;
	for (int i = 0; i < n; i++) {
		if (max(maxlevel, arr[i]) != maxlevel) {
			maxlevel = arr[i];
		}
		sum += arr[i];
	}

	sum -= maxlevel;
	int result = maxlevel * (n - 1) + sum;

	cout << result << '\n';
	
}