문제 소개 📌

문제 링크 📢

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

문제 풀이 📝

조별로 티셔츠를 맞추는 비용을 최소화하려면 어떻게 해야할까? 티셔츠를 맞추는 비용은 조 내부에서 가장 키가 큰 사람과 작은 사람의 차이다.
따라서 옆사람과의 키 차이를 저장한 뒤, 그 키 차이에서 큰 순서대로 K개만큼 제외해준 다음 제외되지 않은 키 차이들을 전부 더한다면 이것이 조별로 드는 비용이 될 것이다!
주어진 상황에서 최선을 선택하는(가장 큰 키차이부터 제외하는) 그리디한 접근방식과 정렬을 사용하면 풀 수 있는 문제였다.

코드

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

using namespace std;

vector<int> arr;
vector<int> cost;
int N, K;
int main()
{
	cin >> N >> K;
	arr.resize(N);
	cost.resize(N - 1);
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	for (int i = 1; i < N; i++)
	{
		cost[i - 1] = arr[i] - arr[i - 1]; // 키 차이 저장
	}
	sort(cost.begin(), cost.end());
   
	long long ans = 0;
   
	for (int i = 0; i < N - K; i++)
	{
		ans += cost[i];
	}
	cout << ans;

	return 0;
}