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

그리디를 활용해서 풀면 되는 문제이다. 

 

#접근방법

 

그리디의 공통은 어떻게 하면 최적의 값을 구할 수 있는지 알아채야한다. 

해당 문제 같은경우에는 문제를 잘 이해해서 의도를 파악해야한다. 

 

level 값이 만약 , 

 

10 40 50 20 70 20 10 

 

이런식으로 주어진다면, 어떻게 합을 하면 최댓값을 찾을 수 있을까 고민해야한다. 

 

위의 예제에서 가장 큰 레벨의 값은 70이다. 

그렇다면 70에다가 주변에 있는 레벨 값을 다 더해서 생성되는 것이 최대이지않을까? 라는 생각을 하는 순간, 바로 풀 수 있다. 

 

즉, 배열에서 가장 큰 레벨을 가진 값과 인덱스 번호를 저장을 한 다음에 

그 값을 기준으로 해서 다른 레벨의 값들을 더해서 만들어진 값들이 최댓값이 된다. 

 

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

int main() {
	int n; cin >> n; 
	vector<int> v(n);
	int max_n = -1;
	int idx = 0; 
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		if (max_n < v[i]) {
			idx = i; 
			max_n = v[i]; 
		}
	}
	int result = 0; 
	for (int i = 0; i < idx; i++) {
		result += v[i]+v[idx]; 
	}
	for (int i = idx + 1; i < n; i++) {
		result += v[i] + v[idx]; 
	}
	cout << result; 

}

 

12845번: 모두의 마블