(매일 BOJ) C++ 7568번 덩치

이번 문제는 실버 5 난이도의 7568번 덩치문제이다.

문제의 접근법부터 살펴보자.

입력이 X Y의 형태로 N개 주어지기 때문에, 2차원 배열을 이용해야 함을 알 수 있다.

그리고 문제에서 힌트를 준 것을 잘 살펴보면, 브루트포스를 사용하여 완전탐색을 한 후 자기 자신보다 큰 값이 몇개인지를 카운트 하고 이를 바로바로 ' '로 출력하면 됨을 볼 수 있다.

 

시간제한이 1초 (연산 100,000,000회), N이 최대 50이며, for 반복문 3회 O(n^3) 50^3 의 연산을 2회 50^3*2 진행하니, 대략 계산해보면 50*50*50*2 최대 250,000번의 연산이 진행되는 것을 볼 수 있으며 따라서  vector 를 사용해도 TLE 가 발생하지 않는 것을 쉽게 알 수 있을 것이다.

 

아래는 작성한 코드이다.

#include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);

    int N;
    cin >> N;

    vector<vector<int>> list(N, vector<int>(2));
    for (int i = 0; i < N; i++){
        for (int j = 0; j < 2; j++){
            cin >> list[i][j];
        }
    }
    for (int i = 0; i < N; i++){
        int r = 1;
        for(int j = 0; j < N; j++){   
            if (list[i][0] < list[j][0] && list[i][1] < list[j][1]) r++;
        }
        cout << r << " ";
    }


}

 

다른 사람이 작성한 코드를 보면 pair 을 사용하면 2차원 백터를 만들지 않고도 해결할 수 있는 것을 알 수 있다.

 

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

int main() {
    int num;
    int rank = 1;
    pair<int,int> arr[50];
    cin >> num;
    for(int i = 0; i < num; i++)
        cin >> arr[i].first >> arr[i].second;
    for(int i = 0; i < num; i++)
    {
        for(int j = 0; j < num; j++)
            if(arr[i].first < arr[j].first && arr[i].second < arr[j].second)
                rank++;
        cout << rank << ' ';
        rank = 1;
    }
}