[C++] 백준 13164번 - 행복한 유치원

Greedy하게 풀 수 있는 문제이다. 

아이디어를 한번에 떠올리기가 어려워서 다른분들의 블로그를 참고했다.

사실 아이디어는 여러개가 있었지만 (부분 합 문제 등) 너무 구현이 어려워서 다른 분들의 블로그를 참고했다.

결국 우리가 원하는것은 앞사람과 뒷 사람의 차이(변화량)을 찾는것이다. 따라서 이를 sort시켜서 k-1개 만큼 뽑아내면 된다. 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n, k;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> k;
	vector<int> v(n);
	for (auto& i : v) cin >> i;

	vector<int> diff(n - 1);
	for (int i = 0; i < diff.size(); i++) {
		diff[i] = v[i + 1] - v[i];
	}

	sort(diff.begin(), diff.end(), greater<int>());

	int ans = 0;
	for (int i = k - 1; i < diff.size(); i++) {
		ans += diff[i];
	}

	cout << ans << endl;

	return 0;
}