[C++] 백준 7568번 덩치

1. 문제이해

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

7568번: 덩치

 

A라는 사람이 B라는 사람보다 몸무게와 키가 더 클 때, A의 덩치가 B보다 크다라고 이야기 할 수 있다.

만약, 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다고 할 때,

N명의 사람들의 몸무게와 키가 주어질 때, 각 사람들의 덩치 순위를 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

N명의 몸무게와 키를 입력받아, 각 사람들의 덩치 등수를 출력하는 문제이다.

이 때, 반드시 키와 몸무게 모두가 상대방보다 더 커야 덩치가 크다라고 이야기 할 수 있으며,

둘 중 하나라도 작다면 덩치를 판별할 수 없게 된다. (둘 다 작은 경우, 덩치가 더 작게 된다.)

문제에서 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 되며,

같은 덩치 등수를 가진 사람은 여러명도 가능하다고 했으므로, 이 점에 유의해 아래 예제를 보자.

 

<예제>

 

이름	(몸무게, 키)
A	(55, 185)
B	(58, 183)
C	(88, 186)
D	(60, 175)
E	(46, 155)

위와 같이 5명의 몸무게와 키가 주어졌다고 하자.

문제에서는 자신보다 덩치 큰 사람이 k명이면, 그 사람의 덩치 등수는 k+1이 된다고 했다.

즉, A의 덩치 등수 = A보다 덩치가 큰 사람 + 1 이 된다.

이 점에 착안하여 각 사람들의 덩치 등수를 매겨보면 다음과 같다.

(키와 몸무게 모두 상대방보다 큰 경우에만 덩치가 크다 라고 정의한다.)

 

A보다 덩치가 큰 사람은 C, 1명 이므로, A의 덩치등수 = 1 + 1  = 2 등이 된다.

B보다 덩치가 큰 사람은 C, 1명  이므로, B의 덩치등수 = 1 + 1  = 2 등이 된다.

C보다 덩치가 큰 사람은 없다. 0명  이므로, C의 덩치등수 = 0 + 1  = 1 등이 된다.

D보다 덩치가 큰 사람은 C, 1명  이므로, D의 덩치등수 = 1 + 1  = 2 등이 된다.

E보다 덩치가 큰 사람은 A, B, C, D, 4명  이므로, E의 덩치등수 = 4 + 1  = 5 등이 된다.

 

이를 정리하면 아래 표와 같으며, 예제 출력 1과 동일한 결과가 나오게 된다.

 

이름	(몸무게, 키)	덩치 등수
A	(55, 185)	2
B	(58, 183)	2
C	(88, 186)	1
D	(60, 175)	5
E	(46, 155)	2

 

 

 

3. 소스코드

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

class person {
public:
	int weight;      // 몸무게
	int height;      // 키
	int rank;        // 덩치등수
};

int main() {
	person* p = new person[50];   // 각 사람들의 몸무게와 키
	int N;                        // 전체 사람 수

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> p[i].weight >> p[i].height;
	}

	// 등수는 1부터 시작. 자신보다 덩치가 큰 사람이 있으면 등수를 하나씩 낮춰감.
	for (int i = 0; i < N; i++) {
		p[i].rank = 1;
		for (int j = 0; j < N; j++) {
			if (p[i].weight < p[j].weight && p[i].height < p[j].height) {
				p[i].rank++;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		cout << p[i].rank << " ";
	}

	return 0;
}

먼저, person이라는 class를 두어, 각 사람들의 몸무게, 키, 덩치 등수를 변수로 두었다.

메인 함수에서 이 class person 형식의 배열을 선언하고, 각 사람들의 몸무게와 키를 입력받았다.

 

이후 for 문을 통해, 2. 문제풀이에서 도출한 풀이방식을 적용해 각 사람들의 덩치 등수를 구해주었다.

(A의 덩치 등수 = A보다 덩치가 큰 사람 + 1 )

 

 

---

백준에서 풀이한 여러문제들을 쭉 모아보니, DFS, BFS 문제는 거의 풀지 않았더라..😢

아무래도 약한 부분이기도 하고, 풀이가 어려워서 무의식적으로 피한 것도 있는 것 같다..

한문제씩 도전해보도록 해야지...💪