[백준 18869] 멀티버스 2 (C++)

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

18869번: 멀티버스 Ⅱ

---

멀티버스 2 문제의 해결 방법은 2가지가 있습니다. 

 

정렬을 이용한 방법

---

먼저, 첫번째 방법은 아래와 같습니다. 

문제에서는 아래와 같은 조건을 만족하면, 두 우주가 균등하다고 합니다.

1. Ai < Aj → Bi < Bj
2. Ai = Aj → Bi = Bj
3. Ai > Aj → Bi > Bj

따라서 대소 관계가 동일하면 두 우주가 균등하다고 할 수 있습니다. 

먼저, 두 우주 A, B를 정렬하고, 정렬 후의 우주를 각각 X, Y라고 하겠습니다.

그럼 두 우주가 균등하다면, X, Y의 같은 인덱스의 요소는 정렬 전의 위치가 같아야합니다. 

 

예를 들면, A = {1, 3, 2}이고, B = {12, 50, 31}이면, 정렬 후, X = {1, 2, 3}이고, Y = {12, 31, 50}입니다. 

1. X[0] = 1의 정렬 전 위치는 0이고, Y[0] = 12의 정렬 전 위치는 0입니다.
2. X[1] = 2의 정렬 전 위치는 2이고, Y[1] = 31의 정렬 전 위치는 2입니다.
3. X[2] = 3의 정렬 전 위치는 1이고, Y[2] = 50의 정렬 전 위치는 1입니다.

따라서 두 우주는 균등하다고 할 수 있습니다.

하지만, 아래의 테스트 케이스의 경우 위의 solution이 동작하지 않습니다. 

2 5
1 1 1 2 3
1 1 1 1 2

이미 정렬된 두 우주에 대해서는 항상 균등하다고 판단하기 때문입니다. 

따라서 (X[i] < X[i + 1]) == (Y[i] < Y[i + 1])을 만족하는지 추가해줘야합니다. (단, X, Y는 오름차순 정렬된 상태)

 

아래는 정렬을 이용한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;
 
#define size first
#define idx second
 
pair<int, int> u[101][10010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int m, n; cin >> m >> n;
    for(int i = 0; i < m; i++){
        for(int j = 0, size; j < n; j++){
            cin >> size;
            u[i][j] = {size, j};    // {행성의 크기, 정렬 전 인덱스}
        }
        sort(&u[i][0], &u[i][n]);   // 각 우주를 행성 크기를 기준으로 정렬
    }
 
    int ans = 0;    // 균등한 우주 쌍의 개수
 
    for(int i = 0; i < m - 1; i++){
        for(int j = i + 1; j < m; j++){ // 두 우주를 선택 (Combination)
            bool equal = true;  // 두 우주가 균등한지 나타내는 Flag 변수
            for(int k = 0; k < n; k++){
                if(u[i][k].idx != u[j][k].idx) {    // 정렬 전 위치가 같지 않다면
                    equal = false;  // 두 우주는 균등하지 않은 우주
                    break;
                }else{  // 정렬 전 위치가 같다면
                    if(i != n - 1){
                        if(u[i][k].size < u[i][k + 1].size != u[j][k].size < u[j][k + 1].size){ // 대소관계 비교
                            equal = false;
                            break;
                        }
                    }
                }
 
            }
            if(equal) ans++;
        }
    }
    cout << ans << "\n";
}

 

좌표 압축을 이용한 방법

---

좌표 압축은 수의 값에 무관하게 좌표 사이의 대소만 알면 될 때, 좌표 압축을 이용하여 수의 범위를 줄여줄 수 있습니다.

따라서, 두 우주가 균등하다면 좌표 압축 결과가 같습니다.

 

좌표 압축은 

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있을 때,

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수입니다.

 

예를 들어 A = {1000, 999, 1000, 999, 1000, 999}는 좌표 압축 결과 A = {1, 0, 1, 0, 1, 0}이 됩니다.

 

아래는 좌표 압축을 이용한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> u(101, vector<int>(0));
 
void compression(vector<int>& v){   // 벡터에 대해 좌표 압축을 수행하는 함수
    vector<int> tmp(v.size()); 
    copy(v.begin(), v.end(), tmp.begin());  // v를 tmp 벡터에 copy
 
    sort(tmp.begin(), tmp.end());   // tmp 벡터를 오름차순 정렬
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());   // 중복 제거
 
    for(int i = 0; i < v.size(); i++){  // X'i 계산
        int idx = lower_bound(tmp.begin(), tmp.end(), v[i]) - tmp.begin();  
        v[i] = idx;
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int m, n; cin >> m >> n;
    for(int i = 0; i < m; i++){
        for(int j = 0, size; j < n; j++){
            cin >> size;
            u[i].push_back(size);
        }
        compression(u[i]);  // 각각의 우주에 대해 좌표 압축 수행
    }
 
    int ans = 0;
    for(int i = 0; i < m - 1; i++){
        for(int j = i + 1; j < m; j++){ // 두 우주가 균등한지 확인 (Combination)
            if(u[i].size() == u[j].size()){ // 좌표 압축 후, 좌표의 개수가 같을 때만 균등할 수 있음
                bool equal = true;  // 두 우주가 균등한지를 나타내는 Flag 변수
                for(int k = 0; k < u[i].size(); k++){   // 각각의 좌표 압축 결과를 비교
                    if(u[i][k] != u[j][k]) equal = false;   // 결과가 다르다면, 두 우주가 균등하지 않은 것
                }
                if(equal) ans++;
            }
        }
    }
    cout << ans;
}