[백준 31845] 카드 교환 (C++)

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

문제

인하대학교 축제가 열리면, 인천 최대 규모의 카지노인 인하 카지노도 함께 문을 연다. 손님들의 더 많은 유입을 원했던 인하 카지노는 모두가 즐길 수 있는 새로운 카드 게임을 만들었다. 새로운 카드 게임의 진행 방식은 다음과 같다.

딜러와 플레이어는 각각 1부터 N까지의 정수가 적힌 카드를 한 장씩 받는다. 딜러는 아무것도 적혀있지 않은 더미 카드 한 장을 추가로 받는다. 그리고 플레이어는 가진 점수가 0인 상태에서 게임을 시작하여 턴을 M회 수행한다. 각 턴은 아래와 같은 순서대로 진행된다.

1. 플레이어가 딜러의 패에서 원하는 카드를 하나 가져온다.
2. 플레이어의 패에서 같은 값을 가진 카드 쌍이 만들어진 경우, 그 카드 쌍은 패에서 제거된다. 그리고 해당 카드 쌍에 적힌 값이 i라면 플레이어는 Ai점을 얻는다. 얻는 점수가 음수일 수 있으며, 플레이어의 점수도 음수가 될 수 있다.
3. 플레이어가 딜러에게 자신의 패에서 원하는 카드를 하나 준다.
4. 딜러의 패에서 같은 값을 가진 카드 쌍이 만들어진 경우 그 카드 쌍은 패에서 제거된다. 이 경우 플레이어는 점수를 얻지 못한다.

 M번째 턴을 끝내거나 더미 카드를 제외한 모든 카드 쌍이 사라진 순간 게임이 종료된다. 즉, 턴이 수행되는 도중이라도 플레이어가 딜러에게 카드를 줄 수 없다면 게임이 즉시 종료된다.

이 카드 게임에서 게임이 종료되었을 때 플레이어가 얻을 수 있는 최대 점수를 구하는 프로그램을 작성해 보자.

 

입력

---

첫 번째 줄에 정수가 적힌 카드의 수 N과 게임의 최대 턴 수 M이 공백으로 구분되어 주어진다.

두 번째 줄에 각 카드에 대해 플레이어의 패에 카드 쌍이 만들어질 때 얻을 수 있는 점수 A1, A2, ⋯, AN이 공백으로 구분되어 주어진다.

 

출력

---

플레이어가 얻을 수 있는 최대 점수를 출력한다.

제한

---

•  1 ≤ N ≤ 1,000
•  1 ≤ M ≤ 1,000
•  −1,000 ≤ Ai ≤ 1,000
•  Ai는 정수이다.

문제 풀이

---

그리디 문제.

 

플레이어가 딜러의 카드를 가져옴으로써 점수를 얻고, 그 이후에 플레이어가 딜러에게 원하는 카드를 한 장 내어주는 방식이다. 플레이어는 현재 남은 카드 중 Ai가 가장 큰 값을 가진 카드를 가져와 점수를 얻고, Ai가 가장 작은 카드를 내어줌으로써 '버리는 카드'로 사용하면 큰 점수를 얻을 수 있다. 이 과정에서 한 턴에 2쌍의 카드가 제거되므로 최대 턴은 (N+1) / 2 턴이 된다. 현재 남은 카드 중 Ai가 가장 큰 값이 0보다 작다면 딜러로부터 가져오는 것이 손해다. 따라서 더미 카드를 가져오고 더미 카드를 내어줌으로써(다음 턴에도 더미 카드를 가져와야 하므로 내어주는 카드도 항상 더미카드여야 한다) 턴을 소모해주면 된다.

 

아래는 코드.

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

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

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