[백준 20300] 서강근육맨 (C++)

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

문제

---

로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.

헬스장에 있는 N개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 10개의 운동기구가 있을 경우 PT를 5번 받으면 모든 기구를 다 사용할 수 있다. 9개의 운동기구가 있는 경우에도 PT를 5번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.

하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 M을 넘지 않도록 하고 싶다. 이때, M의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.

 

입력

---

첫째 줄에 서강헬스클럽에 비치된 운동기구의 개수를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 10 000)

둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수 t1,t2,⋯,tN가 주어진다. (0 ≤ ti ≤ 1018)

출력

---

 M의 최솟값을 출력한다.

 

 

문제 풀이

---

정렬 + 그리디 문제.

 

2개를 합해 최대한 작은 숫자가 나오도록 하면 된다. 작은 것끼리 합하면 나중에는 결국 큰 것이 남게 되므로, 가장 좋은 방법, 즉 정답을 구하는 방법은 남는 것 중 가장 작은 것과 가장 큰 것을 더하는 것이다. N이 홀수라면 가장 큰 것은 제외하고, 2개씩 짝지으면 된다. 2개씩 짝지은 것 중 합이 가장 큰 것(N이 홀수일 때는 가장 큰 것과 비교하여)을 출력해주면 답이 된다.

 

아래는 코드.

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

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

	int N;
	long long answer = -1;
	cin >> N;
	long long* arr = new long long[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	if (N % 2 == 0)
	{
		for (int i = 0; i < N / 2; i++)
		{
			int j = N - 1 - i;
			answer = max(answer, arr[i] + arr[j]);
		}
	}
	else
	{
		answer = arr[N - 1];
		for (int i = 0; i < N / 2; i++)
		{
			int j = N - 2 - i;
			answer = max(answer, arr[i] + arr[j]);
		}
	}
	cout << answer << "\n";
	return 0;
}