[Baekjoon/C++] 25631번 - 마트료시카 합치기

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

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

 

입력

첫째 줄에 마트료시카의 개수 N(1 <= N <= 1000)이 주어진다.

둘째 줄에 정수 a_1, a_2, ... , a_N이 주어진다. a_i(1 <= a_i <= 10^9)는 i번째 마트료시카의 크기이다.

 

출력

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

 

---

풀이

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

int N;
vector<int> arr;
unordered_map<int, int> m;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;

		m[n]++;

		if (m[n] == 1) arr.push_back(n);
	}

	sort(arr.begin(), arr.end());

	int n = m[arr[0]]; // 작은 마트료시카의 수

	for (int i = 1; i < arr.size(); i++) {
		N -= min(n, m[arr[i]]);	// 마트료시카 합치기
        
        	// 작은 마트료시카의 수 갱신하기
		n -= min(n, m[arr[i]]);
		n += m[arr[i]];
	}

	cout << n << '\n';

	return 0;
}