백준] 7568 - 덩치(한국정보올림피아드 2013;KOI 2013 지역본선)

시간 제한 : 1초

메모리 제한 : 128MB

입력

첫 줄에는 전체 사람의 수 N이 주어진다. 그리고 이어지는 N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 각각 나타난다. 단, 2 ≤ N ≤ 50, 10 ≤ x,y ≤ 200 이다.

출력

여러분은 입력에 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단 각 덩치 등수는 공백문자로 분리되어야 한다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct person {
	int weight;
	int height;
	int bigger;
	int originIdx;
};
int compareBigger(const struct person a, const struct person b)
{
	return a.bigger < b.bigger;
}
int compareIdx(const struct person a, const struct person b)
{
	return a.originIdx < b.originIdx;
}
int main(void)
{
	int n;
	cin >> n;
	vector<struct person> arr(n);
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i].weight >> arr[i].height;
		arr[i].originIdx = i;
		arr[i].bigger = 0;
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (arr[i].weight > arr[j].weight && arr[i].height > arr[j].height)
				arr[j].bigger++;

	sort(arr.begin(), arr.end(), compareIdx);
	for (int i = 0; i < n; i++)
		cout << arr[i].bigger + 1 << ' ';
}

Tip

브루트 포스로 해결 가능한 문제다. N의 크기가 그리 크지 않기 때문에, 자신보다 덩치가 큰(키도 크고 몸무게도 큰)사람들의 를 카운트해둔다. 덩치가 큰 사람의 숫자에 따라 등수가 결정되므로, 별도의 순위 산정이 필요 없다.

예)

덩치가 큰 사람이 아무도 없으면 1등으로 분류한다.

자신보다 덩치가 큰 사람이 4명 있으면, 5등이다.

여기서 자신보다 키만 크거나, 몸무게가 더 나가는 사람이면서 덩치가 큰 사람이 동일하면 같은 등수를 부여받는다.