https://www.acmicpc.net/problem/7568
문제
> 덩치를 키와 몸무게로 표현해 등수를 매겨보려한다.
몸무게가 x kg, 키가 y cm라면 덩치는 (x,y)로 표시된다.
A와 B가 각각 (X,Y), (P,Q)일 때, X>P, Y>Q이면 A가 B보다 덩치가 크다고 한다.
> 만약 C와 D가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 무겁고 키는 C가 더 크므로 덩치만 볼 땐 누가 더 크다고 할 수 없다.
> 덩치 등수는 나보다 큰 사람수 +1이 된다. 그리고 같은 등수를 가진 사람이 여러명도 가능하다.
> N명의 몸무게, 키가 주어졌을 때, 각각의 덩치 등수를 구해라.접근
몸무게와 키를 pair로 받고 모든 사람을 각각 비교해 몸무게와 키가 모두 크면 등수를 올려준다.
문제해결
> pair로 몸무게와 키를 입력받아 body벡터에 N명을 저장한다.
> 기본적으로 모든 사람의 등수를 1등으로 주고 등수를 저장할 벡터를 생성한다.
> 이중 반복문으로 사람을 비교하는데 i와 j가 같으면 나 자신이랑 비교하는거라 불필요하므로 continue로 넘어간다.
> 비교했을 때 만약 몸무게 키 둘다 j보다 작다면 rank값을 증가시켜 등수를 떨어뜨린다. 즉, 나보다 덩치가 큰사람이 있다는 뜻이다.
> 젤 덩치가 큰사람은 해당 조건에 걸리지 않으므로 그대로 1등이 나오고
만약 등수를 가릴 수 없는 사람은 나보다 확실히 덩치가 큰사람 제외하곤 rank값이 변화하지 않으므로 동일한 등수를 가지게 된다.
> 등수를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<pair<int, int>> body(N);
for (int i = 0; i < N; i++)
{
cin >> body[i].first >> body[i].second;
}
vector<int> rank(N, 1);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (i == j)
continue;
else if (body[i].first < body[j].first && body[i].second < body[j].second)
{
rank[i]++;
}
}
}
for (auto& a : rank)
{
cout << a << " ";
}
}
후기
브루트포스가 무겁고 무식해서 쓰기 싫어 이런저런 방법을 해봤다. 몸무게, 키별 각 등수를 뽑아 그 등수가 같으면 해당 등수를 가지고 다르면 비교할 수 없는 사람이 있다는 뜻이므로 둘중에 더 큰 등수를 자기 등수로 가지고해서 하려고 했다.
결과적으로 답은 맞더라도 논리에 어긎나 안됐다.
브루트포스가 성능은 그래도 든든하다.
