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

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

18869번: 멀티버스 Ⅱ

 

문제

---

M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.

두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, ..., AN, 우주 B에 있는 행성의 크기는 B1, B2, ..., BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.

• Ai < Aj → Bi < Bj
• Ai = Aj → Bi = Bj
• Ai > Aj → Bi > Bj

입력

---

첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.

 

출력

---

첫째 줄에 균등한 우주의 쌍의 개수를 출력한다.

 

제한

---

• 2 ≤ M ≤ 100
• 3 ≤ N ≤ 10,000
• 1 ≤ 행성의 크기 ≤ 1,000,000

 

문제 풀이

---

좌표 압축 문제.

대소 비교만 하면 되므로 한 우주에 있는 행성들을 오름차순 정렬한 후 각 행성의 크기를 정렬 후의 인덱스로 변환한다. lower_bound를 통해 같은 값은 같은 인덱스를 갖도록 한다.

모든 우주를 오름차순 정렬하면 입력받은 순서의 벡터가 작은 것부터 앞에 오고, i번째 우주와 다른 우주를 비교했을 때 하나라도 인덱스의 값이 다르다면 균등한 우주가 아니다. 모든 우주를 정렬해놓았으므로 비교 대상이 균등한 우주가 아니라면 그 이후의 우주들은 모두 i번째 우주와 균등한 우주가 될 수 없으므로 flag를 통해 반복문을 빠져나간다.

 

아래는 코드.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	int num;
	int answer = 0;
	cin >> N >> M;
	vector<int>* arr = new vector<int>[N];
	for (int i = 0; i < N; i++)
	{
		vector<int> indexes;
		vector<int> temp;
		for (int j = 0; j < M; j++)
		{
			cin >> num;
			indexes.push_back(num);
			temp.push_back(num);
		}
		sort(indexes.begin(), indexes.end());
		for (int j = 0; j < M; j++)
		{
			int index = lower_bound(indexes.begin(), indexes.end(), temp.at(j))- indexes.begin();
			arr[i].push_back(index);
		}
	}
	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			bool isDiff = false;
			for (int k = 0; k < M; k++)
			{
				if (arr[i].at(k) != arr[j].at(k))
				{
					isDiff = true;
					break;
				}
			}
			if (isDiff == true)
			{
				break;
			}
			else
			{
				answer++;
			}
		}
	}
	cout << answer << "\n";
	return 0;
}