[그리디 #3] 카드 합체 놀이

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

15903번: 카드 합체 놀이

 

---

접근 방법

예제를 보면 쉽게 해결할 수 있는 문제이다. 최종적으로 모든 카드의 합이 최소가 되어야 한다.

최소가 되기 위해선 당연하게 가장 작은 카드 2개를 선택하면 된다.

매우 간단하게 해결할 수 있는 그리디 문제이다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long> v;
int n, m;

int main() {
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		long tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	for (int i = 0; i < m; i++) {
		sort(v.begin(), v.end());
		long sum = v[0] + v[1];
		v[0] = sum;
		v[1] = sum;
	}

	long sum= 0;
	for (int i = 0; i < n; i++)
		sum += v[i];
	cout << sum;
}

더했을 때 합이 꽤 커지기 때문에 int보다 더 넓은 범위를 나타낼 수 있는 long을 사용하였다.