백준 7568_덩치(C++)

 

https://www.acmicpc.net/problem/7568

7568번: 덩치

[문제 풀이]

문제의 해결법은 브루트 포스였던 것 같습니다.

단순 브루트 포스를 이용하여 풀었습니다.

반복문을 이용하여 자신보다 덩치가 큰(몸무게와 키가 둘 다 큰) 사람의 개수를 찾을 때마다 증가시켜주는 식으로 문제를 풀었습니다.

 

이 코드의 핵심은

v[i].first < v[j].first && v[i].second < v[j].second

입니다.

[코드]

#include<iostream>
#include<vector>

int N;

vector<pair<int, int>> v;

int main() {

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		int a, b;
		scanf("%d %d", &a, &b);

		v.push_back(make_pair(a, b));
	}

	for (int i = 0; i < N; i++) {

		int count = 1;

		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++;
		}

		printf("%d ", count);
		count = 1;
	}
}

 

 

 

 

 

ps) Sorting을 하여서 순차적으로 등수를 매기는 방법으로 문제를 풀어 보았지만 틀렸습니다. 혹시 어떤 부분이 틀린 건지 아시는 분은 댓글 남겨주시면 감사하겠습니다. 

 

#include<iostream>
#include<vector>
#include<tuple>
#include<algorithm>

using namespace std;

int N;
int grade[51];

vector<tuple<int, int, int>> person;


int main() {

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		person.push_back(make_tuple(a, b, i));
	}

	sort(person.begin(), person.end(), greater<tuple<int,int, int>>());

	int level = 1, count = 1;

	for (int i = 0; i < person.size() - 1; i++) {

		if (get<0>(person[i]) > get<0>(person[i + 1]) && get<1>(person[i]) > get<1>(person[i + 1])) {
			grade[get<2>(person[i])] = level;
			level += count;
			count = 1;

			if (i == person.size() - 2)
				grade[get<2>(person[i + 1])] = level;
		}
		else {
			grade[get<2>(person[i])] = level;
			count++;
			
			if (i == person.size() - 2)
				grade[get<2>(person[i + 1])] = level;
		}
	}

	for (int i = 0; i < N; i++)
		printf("%d ", grade[i]);

	return 0;

}