백준 7568 (C++) 덩치

n의 입력이 작기 때문에 브루트포스(완전 탐색)으로 풀어도 무리가 없다.

자신보다 키, 몸무게 둘 다 큰 경우 cnt++한다.

 

 

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

7568번: 덩치

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> v;
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,x, ans = 0;
    cin >> n;
    for (int i= 0; i < n; i++) {
        int a,b;
        cin >> a >> b;
        v.push_back({a,b});
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (v[i].first < v[j].first && v[i].second < v[j].second) {
                ans++;
            }
        }
        cout << ans+1 << " ";
        ans = 0;
    }
    return 0;
}

 

해당 코드의 시간 복잡도는 O(N^2)이다.