[백준 25631] 마트료시카 합치기 (C++)

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

 

문제

---

마트료시카는 속이 비어있는 인형이다. 성빈이는 𝑁개의 마트료시카를 가지고 있다. 𝑖번째 마트료시카의 크기는 𝑎𝑖이고, 마트료시카 속은 모두 비어있다.

성빈이는 남아 있는 마트료시카 중에서 𝑖번째와 𝑗번째(𝑖≠𝑗)마트료시카를 고른 뒤에 𝑖번째 마트료시카를 𝑗번째 마트료시카 속에 넣을 수 있다. 단, 𝑗번째 마트료시카의 속이 비어있어야 하고, 𝑖번째 마트료시카보다 𝑗번째 마트료시카가 더 커야 한다. 합친 후에는 남아 있는 마트료시카의 개수가 한 개 줄어든다.

성빈이는 마트료시카를 최대한 합쳐서 정리하려고 한다. 성빈이가 마트료시카를 잘 합친다면 남아 있는 마트료시카의 최소 개수는 얼마일까?

 

입력

---

첫째 줄에 마트료시카의 개수 𝑁(1 ≤ 𝑁 ≤ 1 000)이 주어진다.

둘째 줄에 정수 𝑎1,𝑎2,...,𝑎𝑁이 주어진다. 𝑎𝑖(1 ≤ 𝑎𝑖 ≤ 109)는 𝑖번째 마트료시카의 크기이다.

 

출력

---

남아있는 마트료시카의 최소 개수를 출력한다.

 

문제 풀이

---

그리디 문제.

마트료시카 하나 당 그것보다 큰 마트료시카가 있다면 그 마트료시카 안에 넣을 수 있다. 따라서 정렬이 필요하다.

잘보면 답은 같은 값을 가지는 수의 개수의 최댓값이 된다. 한 마트료시카가 다른 크기의 마트료시카 안에 넣을 수 있거나, 그 마트료시카가 반복해서 넣는 마트료시카의 최종이 되기 때문이다.

upper_bound()와 lower_bound()를 사용하면 쉽게 해결할 수 있다.

 

아래는 코드.

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

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

	int N;
	int answer = 0;
	cin >> N;
	int* arr = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
	{
		int count = upper_bound(arr, arr + N, arr[i]) - lower_bound(arr, arr + N, arr[i]);
		answer = max(answer, count);
	}
	cout << answer << "\n";
	return 0;
}