[백준 7568번] 덩치

문제 링크: 7568번 덩치

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

 

모든 경우를 일일이 탐색하는 문제였는데

조금 빠른 속도를 내보겠다고 잘못된 선택을 했다.

 

처음에 시도한 방식은 다음과 같다.

<x, y>에서 x+y를 통해 정렬한 후 위아래로 2개씩 비교하면서

덩치 등수를 크게 하거나, 그대로 두었다.

 

하지만 다음과 같은 반례가 존재한다.

<25, 35>, <10, 30>, <20, 20>, <30, 10>과 같은 경우에는 정렬 여부에 따라서 덩치 등수가 달라진다.

 

올바른 풀이는 다음과 같다.

 

#include <iostream>
using namespace std;
int main(void) {
    // declare
    int n; cin >> n;
    int *xarr = (int *)(malloc(sizeof(int)*n));
    int *yarr = (int *)(malloc(sizeof(int)*n));

    // input
    for (int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        xarr[i] = x;
        yarr[i] = y;
    }

    // search
    for (int i = 0; i < n; i++) { // arr[i]의 등수를 구할 것이다.
        int higher = 0; // arr[i]보다 큰 덩치를 가진 사람 수
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            if (xarr[i]<xarr[j] && yarr[i]<yarr[j]) {
                higher++;
            }
        }

        int rank = higher + 1;
        cout << rank << ' ';
    }

    return 0;
}