백준 7568번 - 덩치

C++

7568번 - 덩치

문제

학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력하는 문제 출처

초기 접근 및 실패

처음에 pair<몸무게, 키>를 통해 몸무게를 기준으로 내림차순으로 정렬 한 뒤, 졍렬한 기준에서 키가 바로 위의 사람과 비교하여 더 작을시 덩치 등수를 계산하는 방법으로 구현을 하였습니다. 하지만 이는 반례가 존재하는데,

| input |output|answer|
|-------|------|------|
|170 75	|  1   |  1   |
|130 16	|  3   |  3   |
|180 75	|  1   |  1   |
|120 156|  3   |  1   |
|49 24  |  5   |  4   | 

보시는 것과 같이, OutPut과 실제 답이 다른 것을 알 수 있습니다. 이는, 위의 예에서, 몸무게 순으로 정렬을 하면,

180 75	1
170 75	1
130 16	3
120 156	3
49 24	5

가 된다. 이는 4번째의 (120, 156)인 사람이 (130, 16)인 사람과 비교를 하기 때문입니다. 또한 (49,24)는 (130, 16)과 비교를 할 수 없어 4가 되어야 하지만, 위의 알고리즘으로는 (120,156)과 비교를 하게 되어 5가 됩니다.

접근 방법 및 구현

간단히 완전 탐색으로 생각 하되, 자신 보다 덩치가 큰 사람이 발견시 자신의 순번을 올리는 방식으로 구현을 하면 된다.

코드

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

int n;
vector<pair<pair<int, int>,int>> man;	//pair 내부의 pair를 통해 몸무게, 키, 순번을 저장할 vector를 선언한다.
int a, b;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a;
		cin >> b;
		man.push_back(make_pair(make_pair(a, b),1));	//초기 순번은 다 1이다.
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j)
				continue;
			//만일 자신보다 덩치가 큰 사람이 존재 할 시, 자신의 순번을 1올린다.
			if (man.at(i).first.first < man.at(j).first.first && man.at(i).first.second < man.at(j).first.second) {
				man.at(i).second++;
			}
		}
	}


	for (int i = 0; i < n; i++) {
		cout << man.at(i).second << " ";
	}
	cout << "\n";
	
	return 0;
}

후기 및 개선할 점

후기: 집중!