[백준/C++] 알고리즘 18869번 - 멀티버스 II

안녕하세요! 테크지니어22입니다.

 

오늘은 백준 알고리즘 18869번 - 멀티버스 II를 풀어보도록 하겠습니다.

 

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

18869번: 멀티버스 Ⅱ

[문제 접근]

우주가 균등하다는 조건을 그대로 이용하려고 했는데, 잘 안되었습니다. 결국 좌표압축이라는 개념을 알아야하더라구요.

간단히 좌표압축이란 좌표의 값과 무관하게 좌표들 사이의 대소관계만 필요할 때 사용하는 테크닉입니다. (메모리 공간을 절약할 수 있음)

우주가 균등하다는 조건을 다시 생각해보면, 좌표들 사이에 대소관계라는 것을 파악할 수 있습니다. 즉 좌표압축을 이용해야 합니다.

 

정리하면

우주가 균등하다 = 좌표들 사이의 대소관계가 같다 = 압축된 좌표가 같다. 

이렇게 되겠네요.

 

좌표를 압축시킨 후에는 이중 for문을 사용해서 균등한 우주 쌍의 개수를 세면됩니다.

 

[풀이 전략]

1. 좌표압축 테크닉을 이용한다.

2. 이중 for문을 이용하여 균등한 우주 쌍의 개수 파악한다.

 

[코드]

// 멀티버스 2

int m, n; // 우주의 개수, 행성 개수

int arr[102][10002];
int cnt ; 


// 좌표 압축
void compress(int a[]) {
    vector<int> v(a, a+n);
    sort(v.begin(), v.end()); // 오름차순 정렬
    v.erase(unique(v.begin(), v.end()), v.end()); //unique는 연속적으로 존재하는 요소들을 삭제 해준다. but 배열의 사이즈는 그대로이기 때문에 뒷부분 제거 .
    for (int i = 0; i < n; i++)
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
}

// 비교
bool cmp(int a[], int b[]) {
    for(int i = 0; i < n ; i++)
        if(a[i] != b[i]) return false ;
    return true;
}

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> m >> n ;
    for(int i = 0 ; i < m ; i++) {
        for(int j = 0 ; j < n ; j++){
            cin >> arr[i][j] ;
        }
        compress(arr[i]);
    }
    for (int i = 0; i < m - 1; i++)
        for (int j = i + 1; j < m; j++)
            cnt += cmp(arr[i],arr[j]);
    cout << cnt ; 

}

 

[배울 점]

- 공간복잡도 512MB -> 1.2억개 

- 좌표압축 개념