[백준 27277] 장기자랑 (C++)

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

문제

---

즐거운 설날을 맞아 부대 장기자랑 행사가 개최된다! 이 행사는 한 번에 한 명씩 순서대로 공연하는 형식으로 진행된다.

장기자랑 행사의 총관리자는 공연하는 병사들의 장기자랑 실력을 토대로 행사를 준비하던 중, 아무래도 앞에 공연한 사람이 너무 잘하면 뒤에 공연하는 사람이 부담감을 느껴 본 실력을 발휘하지 못할 것이라는 고민을 하게 되었다. 이에 총관리자는 각 병사의 장기자랑 실력을 순서대로 a1,a2,⋯,an이라고 할 때, 2 ≤ i ≤ N에 대하여 i번째 공연자는 실력을 max(0,ai−ai−1)만큼만 발휘할 수 있을 것이라는 가설을 세웠다. 이때, 가장 먼저 공연하는 병사는 본인의 실력을 그대로 발휘할 수 있다.

위 가설에 따라, 총관리자는 병사들이 발휘할 수 있는 실력의 합이 최대가 되게끔 공연순서를 배치하고자 한다. 적절한 순서로 병사들을 배치했을 때, 각 병사가 발휘할 수 있는 실력의 합의 최댓값을 구하여라.

 

입력

---

첫 번째 줄에 병사의 수 N이 주어진다. (1 ≤ N ≤ 100000)

두 번째 줄에 N명의 병사들의 장기자랑 실력을 나타내는 정수 ai가 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 10000)

 

출력

---

적절한 순서로 N명의 병사들을 배치했을 때, 각 병사가 발휘할 수 있는 실력의 합의 최댓값을 출력한다.

 

문제 풀이

---

 그리디 문제.

 

이전 참가자보다 실력이 최대한 높아야 실력의 합이 높아질 수 있다. 따라서 가장 실력이 가장 좋지 않은 사람과 가장 실력이 좋은 사람 순서대로 붙여놓으면 가장 좋은 점수를 얻을 수 있다. 정렬 후 가장 실력이 좋은 사람(맨 마지막 순서) - 가장 실력이 좋지 않은 사람 - 그 다음으로 가장 실력이 좋은 사람 - 그 다음으로 가장 실력이 좋지 않은 사람... 순서대로 배치하면 된다.

 

아래는 코드.

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

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

	int N;
	cin >> N;
	int* arr = new int[N];
	int* orders = new int[N];
	int index = 0;
	deque<int> dq;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
	{
		dq.push_back(arr[i]);
	}
	for (int i = N-1; i >=0 ; i--)
	{
		if (index % 2 == 0)
		{
			orders[i] = dq.back();
			dq.pop_back();
		}
		else
		{
			orders[i] = dq.front();
			dq.pop_front();
		}
		index++;
	}
	int answer = orders[0];
	for (int i = 1; i < N; i++)
	{
		answer += max(0, orders[i] - orders[i - 1]);
	}
	cout << answer << "\n";
	return 0;
}