문제 풀이
덩치를 정하는 방법은 (a1, b1) (a2, b2)가 있을 때 a1 > a2 이면서 b1 > b2 이면 앞에 있는 사람이 뒤에 있는 사람보다 덩치가 크다는 의미입니다.
그런데 덩치를 정할 수 없는 순간이 있다면 등수는 모두 같은 것으로 치고, 자신보다 앞에 있는 덩치가 N명이라면 자신의 등수는 N+1로 설정하면 됩니다.
N의 크기가 엄청 작기 때문에 완전 탐색으로 모든 경우의 수를 돌려 자신보다 덩치가 큰 녀석들만 카운트합니다.
최종적으로 자신의 등수는 카운트 + 1로 설정합니다. 자신보다 더 큰 덩치가 없다면 자신이 제일 크기 때문에 1등으로 처리해야 되기 때문이죠.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<pair<int, int> > v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i].first >> v[i].second;
}
for (int i = 0; i < n; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
if (i == j) continue;
if (v[i].first < v[j].first && v[i].second < v[j].second)
{
count++;
}
}
cout << count + 1 << ' ';
}
cout << endl;
return 0;
}
'Algorithm' 카테고리의 다른 글
[백준 1120] 문자열 (0) | 2021.12.09 |
---|---|
[백준 2960] 에라토스테네스의 체 (0) | 2021.12.07 |
[백준 11866] 요세푸스 문제0 (0) | 2021.12.06 |
[백준 3009] 네 번째 점 (0) | 2021.12.05 |
[백준 10773] 제로 (0) | 2021.12.05 |