글 읽기 - c++)18869 멀티버스2 반례 질문입니다! 도와주세요 ㅜㅜ!

ganzang_dady 2년 전 0

제 코드에 반례를 찾아주실 수 있을까요?

매일매일 눈물을 흘리고 있습니다..

주석을 치렁치렁 달아놨는데 이해가 안가시면 말씀해주세요!

ㅜㅜ... 제가 생각한게 틀린것인지..

#include<bits/stdc++.h>
using namespace std;

vector<int> spaces[102];
vector<int> cmp[102];
vector<int> overlapped[102];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int cntOfPair = 0;
	int n, m;
	cin >> n >> m; // n = 우주의 갯수 / m = 행성의 갯수
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int tmp; cin >> tmp;
			spaces[i].push_back(tmp); // SPACES[I]에는 입력받은 우주들을 저장합니다
		}
		cmp[i] = spaces[i]; // cmp 벡터를 만듬  -  cmp벡터는 순서를 저장하는 놈(좌표압축때쓸꺼)
		overlapped[i] = spaces[i]; // overlap 벡터를 만듬 - overlap 벡터로 중복되는 거 셈
	}
    
	for (int i = 0; i < n; i++) 
		sort(overlapped[i].begin(), overlapped[i].end()); // overlap 벡터를 정렬합니다

	for (int i = 0; i < n; i++) {
		bool isLapped = false; // isLapped 는 중복여부를 판정합니다
		for (int j = i + 1; j < n; j++) {
			if (overlapped[i] == overlapped[j]) { // 구성이 같고 순서가 다른 우주를 발견
				overlapped[i].clear(); // 중복이라면 없애줍니다 - 없애는 이유는 
				isLapped = true;       // ovelapped[i]가 또다른 구성같고 순서다른 
                                       // 중복되는 우주를 만났을때
			}                          // 반복 카운트 되면 안되기 때문입니다
		}
		if (isLapped) // 한쌍만 카운트 한다고 명시되어있으므로 한번만 더해줍니다
			++cntOfPair;
	}

	// cmp를 좌표가 압축된 벡터로 만들기로 결정 ( 평범한 좌표 압축입니다! )
	for (int i = 0; i < n; i++) {
		sort(cmp[i].begin(), cmp[i].end());
		unique(cmp[i].begin(), cmp[i].end()); // 중복되는거 뒤로 뺴주고
		for (int j = 1; j < m; j++) {
			if (cmp[i][j - 1] >= cmp[i][j]) // 중복되는걸 발견
				cmp[i].erase(cmp[i].begin() + j, cmp[i].end()); break; // 그 뒤로는 다 삭제해줌(쓰레기값)
		}
	}

	for (int i = 0; i < n; i++) { // spaces[i]에 좌표 압축된 값을 직접 넣어줬습니다
		for (int j = 0; j < m; j++) {
			int idx = lower_bound(cmp[i].begin(), cmp[i].end(), spaces[i][j])
				- cmp[i].begin(); // idx는 각 우주에서 행성크기를 압축시킬때 쓰는 인덱스입니다
			spaces[i][j] = idx;   // 직접넣어줬습니다
		}
	} // spaces 행성들이 좌표 압축됨

    //// 이 밑으로는 그냥 좌표 압축된 값이 중복되면 출력한다. 입니다
	for (int i = 0; i < n; i++) {		
		for (int j = i + 1; j < n; j++) {
			if (!spaces[j].empty() && spaces[i] == spaces[j]) {
				cntOfPair++;
				spaces[j].clear(); // spaces[j]를 클리어 시키는 이유는 
			}                      // {1,2,3} {10,20,30} {100,200,300}(3쌍)
		}                          // 이 들어오면 그냥 전부 한쌍으로 치려고 없앴습니다
	}
    
	cout << cntOfPair;// 쌍의 갯수를 출력했습니다


	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++)18869 멀티버스2 반례 질문입니다! 도와주세요 ㅜㅜ!

ganzang_dady 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말