[C/C++] 덩치 (백준 7568)

문제

 

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55,173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다.

 

N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다. 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다. 이렇게 등수를 결정하면 같은 덩치 등수를 가진 사람은 여러 명도 가능하다. 아래는 5명으로 이루어진 집단에서 각 사람의 덩치와 그 등수가 표시된 표이다.

 

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

 

위 표에서 C보다 더 큰 덩치의 사람이 없으므로 C는 1등이 된다. 그리고 A, B, D 각각의 덩치보다 큰 사람은 C뿐이므로 이들은 모두 2등이 된다. 그리고 E보다 큰 덩치는 A, B, C, D 이렇게 4명이므로 E의 덩치는 5등이 된다. 위 경우에 3등과 4등은 존재하지 않는다. 여러분은 학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다.

 

예제 입력 1 

 

5
55 185
58 183
88 186
60 175
46 155

 

예제 출력 1

 

2 2 1 2 5

 

풀이

 

처음엔 내가 너무 복잡하게 생각했다. 맵을 사용해서 몸무게와 키를 정리하고 비교를 해서 어떠한 경우에는 등수가 같고 고민을 열심히 하다가 일단 코딩에 들어가고 바로 망해버렸다.

 

그리고 며칠 뒤(오늘) 문제를 다시 풀게 되었는데 역시 쉬고 오면 머리가 좀 돌아가는 것일까 뭔가 머릿속에서 이루어지는 느낌이 들어서 그대로 작성을 하니 한 번에 통과 하였다.

 

코테 책에 있던 방식

 

1. 문제를 적고

2. 어떻게 풀지 정하고

3. 문제를 푼다.

 

이 순서를 정확하게 따라서 했다. 문제는 적었고 어떻게 풀지가 문제인데 이전 처럼 어렵게 생각하지 않았다. 1등이 되는 조건과 2등이 되는 조건 그리고 5등이 되는 조건은 당연히 여기 문제에서 말하는 덩치 차이이다. 하지만 구하는 방법이 잘못된 것 같아서 생각을 해보고 이게 완전 탐색이라면 첫 번째 녀석 부터 탐색을 한다.

 

라는 생각에 다다르니 덩치 비교를 해서 자신의 덩치가 작은 경우를 제외하고는 그냥 넘어가는 방식으로 순위를 높여가면 되지 않을까? 라는 결론에 이르게 되었다.

 

처음 녀석은 <55 , 185>이다.

2번째 <58, 183>로 덩치가 같다. 몸무게는 처음 녀석이 적지만 키는 더 큰(부러운 놈) 그래서 패스

3번째 <88, 186>로 덩치가 처음 녀석이 더 작다. 그러니 rank++;

4번째 <60, 175>로 덩치가 같다. 2번째와 같은 이유로 패스

5번재 <46, 155>로 덩치가 처음 녀석이 더 크다. 하지만 크다는 건 등수에 변함이 없으므로 패스

 

그러니 자동으로 덩치의 상관관계는 결국 맞물리는 거라고 생각해서 여기서 끝이 아닌가? 라는 생각이 들었다.

결론은 탐색을 통해서 나를 제외한 사람들 중 나보다 큰 사람이 있다면 +1 아니라면 그냥 패스로 코드를 짰다.

 

코드

 

#include <iostream>

int main(void){
    int n;
    
    scanf("%d", &n);

    int **a = new int*[n];
    int *answer = new int[n];
    for(int i = 0 ; i < n ; i++){
        a[i] = new int[2];
        int x, y;

        scanf("%d %d", &x, &y);
        a[i][0] = x;
        a[i][1] = y;
    }

    //초기화 완료

    for(int i = 0 ; i < n ; i++){
        int rank = 1;
        for(int j = 0 ; j < n ; j++){
            if(i != j){
                if(a[i][0] < a[j][0] && a[i][1] < a[j][1]){
                    rank++;
                }
            }
        }
        answer[i] = rank;
    }

    for(int i = 0 ; i < n ; i++){
        if(i == 0){
            printf("%d", answer[i]);
        }else{
            printf(" %d", answer[i]);
        }
    }
}

 

끝