[백준 31589] 포도주 시음 (C++)

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

문제

---

산들이는 포도주(와인)를 좋아한다. 그는 마트에서 팔고 있는 N종류의 포도주를 사서 음미하려고 한다. 포도주를 한 병 단위로 사기엔 산들이가 금전적으로 부담이 있기 때문에 그는 작은 용기에 담긴 포도주를 살 것이다. 마트에서 팔고 있는 N종류의 포도주들은 각각 T₁, T₂, …, T_N의 맛을 갖고 있다. 맛의 값이 높은 포도주가 더 맛있는 포도주이다.

산들이가 맛있는 포도주를 마시다가 맛없는 포도주를 마시면 그 맛이 감기약 맛을 방불케 하기 때문에 사실상 0의 맛을 느낀다. 하지만 맛없는 포도주를 마시다가 맛있는 포도주를 마시면 그 두 포도주의 맛 차이만큼 맛을 느낀다. 예외적으로 가장 먼저 마시는 포도주의 맛은 그 포도주 본연의 맛 그대로이다.

산들이는 주량이 매우 적기 때문에 K종류의 포도주를 먹으면 취하여 잠자리에서 뻗어버린다. 따라서 산들이는 N종류의 포도주들 중에서 K종류를 골라 마실 것이다. 산들이는 K종류의 포도주를 마시면서 느낄 수 있는 맛의 합을 극대화하려고 한다.

산들이를 도와 포도주를 얼마나 맛있게 음미할 수 있는지 구하는 프로그램을 작성하여라.

입력

---

첫 번째 줄에는 포도주의 수 N과 산들이의 주량 K가 주어진다. (1 ≤ K ≤ N ≤ 300000)

두 번째 줄에는 N개의 포도주의 맛 T_i가 주어진다. (1 ≤ T_i ≤ 1000000000)

 

출력

---

첫 번째 줄에 산들이가 느끼는 맛의 합의 최댓값을 출력한다.

 

문제 풀이

---

그리디 문제.

 

맛있는 포도주를 먹다 맛없는 포도주를 먹으면 맛은 0이지만, 맛없는 포도주를 먹다 맛있는 포도주를 먹으면 그 차이만큼 맛을 느낄 수 있다. 따라서 남은 것 중 가장 맛있는 포도주를 마시고, 그 후 남은 것 중 가장 맛없는 포도주를 마셔 '버리는 카드'로 사용한다. 그럼 맛있는 포도주 -> 맛없는 포도주 관계에서는 가장 적게 '피해'를 줄일 수 있고, 이 이후에 남은 것 중 가장 맛있는 것을 마시면 맛없는 포도주->맛있는 포도주 관계에서 가장 많은 맛을 느낄 수 있다.

 

다시 말해 가장 맛있는 것 - 가장 맛없는 것 - 가장 맛있는 것 - 가장 맛없는 것... 순으로 마시면 맛의 합이 최댓값을 가질 수 있다.

 

아래는 코드.

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

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

	int N, M;
	cin >> N >> M;
	int* arr = new int[N];
	vector<int> v;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	int bigger = N - 1;
	int smaller = 0;
	for (int i = 0; i < M; i++)
	{
		if (i % 2 == 0)
		{
			v.push_back(arr[bigger]);
			bigger--;
		}
		else
		{
			v.push_back(arr[smaller]);
			smaller++;
		}
	}
	long long answer = v.at(0);
	for (int i = 1; i < M; i++)
	{
		if (v.at(i) > v.at(i - 1))
		{
			answer += v.at(i) - v.at(i - 1);
		}
	}
	cout << answer << "\n";
	return 0;
}