[C++]백준15903번 카드 합체 놀이

오늘은 백준15903번 카드 합체 놀이 문제를 풀어보도록 하자.

우선순위큐로 문제를 풀어 시간복잡도를 줄일 수 있지만 그리디 방식으로 풀어보았다.

문제는 다음과 같다.

                               [접근법]

  1. 카드 값을 벡터에 저장하고 오름차순으로 정렬한다. 

  2. 0번째 + 1번째 값을 더하고 만일 1번째 값이 2번째 값보다 크면 다시 재정렬. 아니면 그냥 넘어간다.
  
  3. 왜냐면 항상 작은 값을 더해서 유지해줘야 하기 때문이다. 만일 4 2 2 1 이라는 값이 들어왔다고 하자. 
  
  오름차순을 하면 1 2 2 5 가 되고 3 3 2 5가 된다. 하지만 3 3을 더하는 것 보단 재정렬 후 ( 2 3 3 5 ) 2 3을 더하는 것이 더 값이 작다. 

                                     [코드]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, m, num;
	long long result = 0;
	vector<long long>v;

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> num;
		v.push_back(num);
	}
	sort(v.begin(), v.end());

	while (m--) {
		v[0] += v[1];
		v[1] = v[0];

		if (v[1] > v[2]) {
			sort(v.begin(), v.end());
		}
	}
	for (int i = 0; i < n; i++) {
		result += v[i];
	}
	cout << result << '\n';
	return 0;
}