[백준 28464] Potato (C++)

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

 

문제

---

감자튀김을 좋아하는 박 모 씨와 다르게, 성우는 감자튀김을 그렇게 좋아하지는 않는다. 어느 날 박 모 씨와 성우는 수많은 감자튀김을 받게 되었고, 이를 나누어 가지기로 했다.

책상 위에 𝑁개의 접시가 놓여있다. 𝑖번째 접시에는 𝑎𝑖개의 감자튀김이 있다. 박 모 씨와 성우는 다음 행동을 번갈아 시행한다.

• 책상 위에 남아있는 접시 하나를 고르고, 접시와 그 위에 놓인 모든 감자튀김을 가져간다.

이는 책상 위의 접시가 모두 사라질 때까지 반복한다. 맨 처음 접시를 가져가는 사람은 박 모 씨다.

박 모 씨는 가져가는 감자튀김의 양을 최대화하려 하고, 성우는 가져가는 감자튀김의 양을 최소화하려 한다. 두 사람이 항상 최선의 행동을 한다고 가정할 때, 성우와 박 모 씨가 최종적으로 가져가는 감자튀김의 양을 구하여라.

 

입력

---

첫 번째 줄에 접시의 개수 𝑁이 주어진다. (1≤𝑁≤200 000)

두 번째 줄에 각 접시에 있는 감자튀김의 개수 𝑎1,𝑎2,⋯,𝑎𝑛가 공백으로 구분되어 주어진다. (1 ≤ 𝑎𝑖 ≤ 10 000)

 

출력

---

첫 번째 줄에 성우가 가져가는 감자튀김의 양과 박 모 씨가 가져가는 감자튀김의 양을 공백으로 구분하여 출력한다.

 

문제 풀이

---

그리디 문제.

박모씨는 남아 있는 접시 중 감자 튀김이 가장 많은 접시를 선택하고, 성우는 남아 있는 접시 중 감자 튀김이 가장 적은 접시를 선택한다. 따라서 내림차순 정렬을 하고, 박 모씨는 앞에서부터, 성우는 뒤에서부터 감자튀김을 가져가면 된다.

박 모씨 먼저 감자튀김을 가져가므로 박모씨는 N+1/2번 가져갈 수 있다. 따라서 0번~ ((N+1) / 2) -1 번 인덱스에 있는 원소들의 합을 모두 더해주면 박 모 씨가 가져가는 양이다.

성우는 ((N+1) / 2)번 인덱스부터 N-1번 인덱스까지 가져가면 된다.

 

아래는 코드.

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

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

	int N;
	cin >> N;
	int* arr = new int[N];
	int pCount = 0;
	int sCount = 0;

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N, greater<>());
	for (int i = 0; i < (N+1)/2; i++)
	{
		pCount += arr[i];
	}
	for (int i = (N + 1) / 2; i < N; i++)
	{
		sCount += arr[i];
	}
	cout <<sCount<<" " << pCount << "\n";
	return 0;
}