BOJ 18869 - 멀티버스 II

18869번: 멀티버스 Ⅱ (acmicpc.net)

18869번: 멀티버스 Ⅱ

 

1차 시도

처음에 각 우주에서 행성 2개씩 비교한 후, 각 위치에 대응하는 비교한 값을 다 더해서 그 갯수로 균등한 우주의 쌍을 구했다. 이 방법은 행성이 4개 이상일 때는 작동하지 않아서 바로 포기했다.

 

접근방법

정렬

각 행성의 인덱스를 저장한 후, 행성의 크기로 Sort를 하게 되면 각 우주에서 행성들의 인덱스 순서는 똑같아진다.

만약 이 행성의 인덱스가 다르면 균등한 우주가 아니다.

 

여기에 예외가 있다

2 5

1 1 1 2 3

1 1 1 1 2

 

위 예제에선 1 < 2 이고 1 < 1이기에 답은 0 이지만, 코드의 출력은 1이 나온다.

이를 해결하기 위해선 행성을 비교할 때, Size를 비교하는 조건도 추가해야 한다.

 

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<map>

using namespace std;

int n,m;
pair<int,int> universe[101][10001];

int main() {
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			int tmp; cin >> tmp;
			universe[i][j] = make_pair(tmp, j);
		}
		sort(&universe[i][0], &universe[i][n]);
	}

	bool flag = false;
	int cnt = 0;
	for (int i = 0; i < m - 1; i++) {
		for (int j = i + 1; j < m; j++) {
			bool flag = false;
			for (int k = 0; k < n; k++) {
				if (universe[i][k].second != universe[j][k].second) {
					flag = true;
					break;
				}
				else {
					if (k < n - 1) {
						if ((universe[i][k].first == universe[i][k + 1].first)
							!= (universe[j][k].first == universe[j][k+1].first)) {
							flag = true;
							break;
						}

					}
				}
			}
			if (!flag)
				cnt++;
		}
	}
	
	cout << cnt;
	return 0;
}