[C++] 백준 7568: 덩치

문제

[C++] 백준 7568: 덩치 SILVER 5
https://www.acmicpc.net/problem/7568

 

---

 

접근 방법

이 문제는 사람들의 몸무게와 키가 주어졌을 때, 각 사람의 덩치 등수를 구하는 문제이다.

 

등수는 단순히 한 가지 기준으로 정렬해서 매길 수 있는 것이 아니라,

어떤 사람 A가 사람 B보다 몸무게도 크고 키도 크면 A가 B보다 덩치가 크다고 판단한다.

즉, 두 조건을 모두 만족해야 비교가 성립한다.

 

처음에는 정렬로 풀려고 했지만, 이 방식은 한 기준으로만 줄을 세우게 되어 “둘 다 큰 경우에만 등수가 밀린다”는 조건을 정확히 반영하지 못해 틀렸다..

그래서 모든 사람을 서로 비교하는 브루트포스(완전탐색) 방식으로 해결했다.

 

각 사람 i에 대해, 다른 사람 j가 i보다 몸무게도 크고 키도 크다면 i의 등수는 1씩 밀리므로
rank를 증가시키는 방식이다.

 

구현 시 주의할 점

• 정렬로 해결하려고 하면 한쪽 기준만 반영되는 경우가 많아 오답이 나기 쉽고, 이 문제는 n ≤ 50이라 완전탐색 O(n^2)로도 충분히 통과한다.
• 등수는 기본이 1등부터 시작하므로 rank = 1로 초기화한다.

 

---

 

코드

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

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

	int n = 0;
	cin >> n;

	vector<pair<int, int>> vect(n);
	for (int i = 0; i < n; i++)
		cin >> vect[i].first >> vect[i].second;

	for (int i = 0; i < n; i++)
	{
		int rank = 1;
		for (int j = 0; j < n; j++)
		{
			if ((vect[i].first < vect[j].first) && (vect[i].second < vect[j].second))
				rank++;
		}
		cout << rank << ' ';
	}

	return 0;
}