ARC_068_B / ABC_053_D - Card Eater #33
Description
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;
}
}