ARC_068_B / ABC_053_D - Card Eater

[zeikar]

Problem link

https://atcoder.jp/contests/arc068/tasks/arc068_b

Problem Summary

수가 적혀진 N개의 카드들이 있다.
카드 중에 3개를 고른 후 가장 작은 수와 가장 큰 수를 빼고 남은 수는 다시 덱에 넣는다.
다른 수의 카드의 개수의 최댓값을 출력하는 문제.

Solution

먼저 3개를 고르고 하나를 다시 집어넣는 연산을 잘 살펴보자.

그냥 아무 두 개의 카드를 제거하는 것과 같다는 것을 알 수 있다.
일단, 각 카드가 한 장밖에 없는 경우는 연산을 하면 안되고, 두 장 이상 있다면 그 두 장을 다 뽑게 되면 나머지 하나는 다시 덱으로 돌아가기 때문이다.

각 카드의 수를 전부 센 다음 제거해야 할 개수를 더한 다음 홀수면 카드의 종류의 수 -1, 짝수면 카드의 종류의 수를 출력하면 된다.

Source Code

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

int main() {
	int n;
	cin >> n;

	map<int, int> cnt;

	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		cnt[a]++;
	}

	int toRemove = 0;
	for (auto& i : cnt)
	{
		if (i.second > 1)
		{
			toRemove += i.second - 1;
		}
	}

	if (toRemove % 2 == 0)
	{
		cout << cnt.size() << endl;
	}
	else
	{
		cout << cnt.size() - 1 << endl;
	}
}