취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25631번 문제인 마트료시카 합치기이다.
문제는 아래 링크를 확인하자.

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

문제에서 주어진 "마트료시카 합치기"는 '비어있는 마트료시카'의 안쪽에 들어가는 다른 마트료시카의 안쪽이 차있는지 여부를 가리지 않음에 유의하자. 즉, 모든 마트료시카의 크기가 다르다면 남아있는 가장 작은 크기의 마트료시카를 두번째로 작은 크기의 마트료시카에 넣는 것을 반복하는 것으로 하나의 마트료시카만이 남아있게 할 수 있다.

한편, 같은 크기의 마트료시카는 서로 넣고 넣어질 수 없다. 따라서 답은 적어도 마트료시카의 크기의 최빈수(mode) 이상임을 알 수 있다.

마트료시카를 최빈수만큼 남기고 항상 합칠 수 있다는 것을 보이는 것은 읽는이에게 맡기겠다.

아래는 제출한 소스코드이다.

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

int N;
int arr[1001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	sort(arr, arr + N);
	int old = -1, cnt = 0, ans = 0;;
	for (int i = 0; i <= N; i++) {
		if (arr[i] == old) cnt++;
		else {
			old = arr[i];
			ans = max(ans, cnt);
			cnt = 1;
		}
	}

	cout << ans;
}