백준 g5 18869 멀티버스 II c++

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

18869번: 멀티버스 Ⅱ

 

문제 설명

M개의 우주가 주어지고, 그 안의 N개의 행성의 크기가 주어진다.

행성들의 인덱스 i, j가 주어질 때, 각각 인덱스들 간의 대소관계가 동일하면 그 우주들은 균등하다.

균등한 우주의 쌍 구하기 (a,b와 b,a는 하나로 친다)

 

예를 들어, 

{1, 3, 2}와 {12, 50, 31}이 있다고 하면 각각 Ai, Aj의 대소 관계가 Bi, Bj의 대소 관계와 동일하므로 두 우주는 균등하다. 

A1 < A2 -> B1 < B2

A1 < A3 -> B1 < B3

A2 > A3 -> B2 > B3

 

풀이

이전에 풀었던 좌표 압축 문제와 유사하다(https://kyj0032.tistory.com/50). 

좌표 압축 문제에서는 key값 미만 값들의 개수를 구함으로써, 숫자들 간의 대소 관계를 나타낼 수 있었다. 

이 문제에도 똑같이 적용해서 본인의 값 미만인 값들의 개수가 같으면 대소 관계가 동일하다고 할 수 있다.

 

수도 코드

space[i][j]: input값, 원본
sorted[i][j]: 좌표 압축 값을 구하기 위해 각 우주 별로 정렬된 값
compress[i][j]: 좌표 압축 값 저장

//1. 좌표 압축
for M: 우주
	for N: 우주 안 행성
    	sorted 배열 정렬
        좌표압축배열 = lower_bound(sorted배열, space[i][j]값 찾기) - sorted[i];

//2. 우주 쌍 비교
for A: 0 ~ M-1 우주
	for B: A+1 ~ M-1 우주 // <- a,b == b,a
    	for N: 우주 안 행성
        	compress[A] == compress[B]인지 검사

 

코드

/*boj g5 18869 멀티버스 II*/
#include <algorithm>
#include <iostream>
#define MAXM 105
#define MAXN 10005
using namespace std;

int M, N;

int space[MAXM][MAXN];
int sorted[MAXM][MAXN];
int compress[MAXM][MAXN];

int main(void) {
    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 >> space[i][j];
        }
    }

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            sorted[i][j] = space[i][j];
        }
    }

    // 1. 좌표 압축
    for (int i = 0; i < M; i++) {
        sort(sorted[i], sorted[i] + N);
        for (int j = 0; j < N; j++) {
            int val = lower_bound(sorted[i], sorted[i] + N, space[i][j]) - sorted[i];
            compress[i][j] = val;
        }
    }
    int ans = 0;
    // 2. 두 개의 우주를 비교
    for (int a = 0; a < M; a++) {
        for (int b = a + 1; b < M; b++) {
            bool flag = true;
            for (int j = 0; j < N; j++) {
                if (compress[a][j] != compress[b][j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) ans++;
        }
    }

    cout << ans << "\n";
}