글 읽기 - 메모리 초과 도와주세요

skesswswkk 3년 전 0

메모리 알맞게 지정한 것 같은데 틀렸네요. 어느 부분에서 메모리가 초과되는지 알려주세요

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int M = 100000 + 5;

int power[M];
int p[M];

int Find(int x) {
	if (p[x] == x) return x;
	return p[x] = Find(p[x]);//
}

void Union(int x, int y) {//if (op == 1) {//동맹
	x = Find(x);
	y = Find(y);

	if (x != y) {//
		p[y] = x;
		power[x] += power[y];
		power[y] = 0;
	}
}

void Union2(int x, int y) {//else if (op == 2) {//전쟁
	x = Find(x);
	y = Find(y);

	if (x != y) {//
		p[y] = x;
		power[x] -= power[y];
		power[y] = 0;
	}
}

int main() {
	//input
	int n, m;
	cin >> n >> m;

	//init
	for (int i = 1; i <= n; ++i) {
		p[i] = i;
	}

	for (int i = 1; i <= n; ++i) {
		int num;
		cin >> num;

		power[i] = num;
	}

	for (int i = 0; i < m; ++i) {
		int op, a, b;
		cin >> op >> a >> b;

		if (op == 1) {//동맹
			Union(a, b);
		}
		else if (op == 2) {//전쟁
			if (power[a] > power[b]) {
				Union2(a, b);
			}
			else if (power[a] < power[b]) {
				Union2(b, a);
			}
			else {
				power[Find(a)] = 0;
				power[Find(b)] = 0;
				p[Find(a)] = 0;
				p[Find(b)] = 0;
			}
		}
	}

	vector<int> v;
	for (int i = 1; i <= n; ++i) {
		if (power[i] > 0) {
			v.push_back(power[i]);
		}
	}
	sort(v.begin(), v.end());

	cout << v.size() << endl;
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i] << " ";
	}
	cout << endl;
}

joonas 3년 전 1

71~72번줄에서 p[Find(a)] = 0 으로 바뀌고 p[Find(b)] 에서 Find(b)가 무한루프를 돌 수 있지 않나요

skesswswkk 3년 전 0

맞았습니다 코드입니다

여기서 28-36 보고 따라한건데 제 코드에선 문제가 되나요?

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

vector<long long> v(100001);
vector<long long> vsize(100001, 1);

// Find 함수로, 각 번호의 루트가 되는 번호를 찾는다.
int Find(int node) {
	if (node == v[node]) {
		return node;
	}
	return v[node] = Find(v[node]);
}
// 루트로 찾은 숫자를 비교하여 다르다면 병합을 실시한다.
void Union(int a, int b) {
	int node1 = Find(a);
	int node2 = Find(b);
	if (node1 != node2) {
		if (vsize[node1] > vsize[node2]) swap(node1, node2);
		vsize[node2] = vsize[node2] + vsize[node1];
		vsize[node1] = 0;
		v[node1] = node2;
	}
}
// 루트가 다르다면 배틀을, 같다면 멸망 시킨다.
void Battle(int a, int b) {
	int node1 = Find(a);
	int node2 = Find(b);
	if (node1 != node2) {
		if (vsize[node1] == vsize[node2]) {
			vsize[node1] = 0;
			vsize[node2] = 0;
			v[node1] = 0;
			v[node2] = 0;
			return;
		}
		else if (vsize[node1] > vsize[node2]) swap(node1, node2);

		vsize[node2] = vsize[node2] - vsize[node1];
		vsize[node1] = 0;
		v[node1] = node2;
	}
}
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		v[i] = i;
	}
	for (int i = 1; i <= N; i++) {
		cin >> vsize[i];
	}
	for (int i = 1; i <= M; i++) {
		int O, P, Q;
		cin >> O >> P >> Q;
		if (O == 1) {
			Union(P, Q);
		}
		else {
			Battle(P, Q);
		}
	}

	//ouput
	vector<int> v;
	int nation = 0;
	// size가 1 이상이면 독립된 국가로 인정한다.
	for (int i = 1; i <= N; i++) {
		if (vsize[i] >= 1) {
			v.push_back(vsize[i]);
		}
	}
	sort(v.begin(), v.end());

	cout << v.size() << endl;
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i] << " ";
	}
	cout << endl;
}

skesswswkk 3년 전 0

@joonas

joonas 3년 전 1

첫 코드에서 71번줄은 72번줄에 영향을 미치지만, 두번째 코드의 35번줄과 36번줄은 독립적이에요.

joonas 3년 전 1

p[Find(a)] = 0 을 수행하고 다시 Find(b) 를 호출하면 p 배열이 어떻게 바뀐 상태에서 다시 계산하는지 그려보시면 좋을 것 같네요.

skesswswkk 3년 전 1

정말 감사합니다!

skesswswkk 3년 전 1

@joonas

문제였던 곳은 62, 65라인이었던 것 같습니다.

power[a] 가 아닌 power[Find(a)] 가 올바른 논리이네요.

도움 주셔서 감사합니다!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int M = 100000 + 5;

int power[M];
int p[M];

int Find(int x) {
	if (p[x] == x) return x;
	return p[x] = Find(p[x]);//
}

void Union(int x, int y) {//if (op == 1) {//동맹
	x = Find(x);
	y = Find(y);

	if (x != y) {//
		p[y] = x;
		power[x] += power[y];
		power[y] = 0;
	}
}

void Union2(int x, int y) {//else if (op == 2) {//전쟁
	x = Find(x);
	y = Find(y);

	if (x != y) {//
		p[y] = x;
		power[x] -= power[y];
		power[y] = 0;
	}
}

int main() {
	//input
	int n, m;
	cin >> n >> m;

	//init
	for (int i = 1; i <= n; ++i) {
		p[i] = i;
	}

	for (int i = 1; i <= n; ++i) {
		int num;
		cin >> num;

		power[i] = num;
	}

	for (int i = 0; i < m; ++i) {
		int op, a, b;
		cin >> op >> a >> b;

		if (op == 1) {//동맹
			Union(a, b);
		}
		else if (op == 2) {//전쟁
			if (power[Find(a)] > power[Find(b)]) {
				Union2(a, b);
			}
			else if (power[Find(a)] < power[Find(b)]) {
				Union2(b, a);
			}
			else {
				power[Find(a)] = 0;
				power[Find(b)] = 0;
				p[Find(a)] = 0;
				p[Find(b)] = 0;
			}
		}
	}

	vector<int> v;
	for (int i = 1; i <= n; ++i) {
		if (power[i] > 0) {
			v.push_back(power[i]);
		}
	}
	sort(v.begin(), v.end());

	cout << v.size() << endl;
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i] << " ";
	}
	cout << endl;
}

joonas 3년 전 0

엇, 거기가 빠졌었군요 ㅋㅋ

그런데 메모리 초과라니.. 무슨 일이었을까요. 해결돼서 다행입니다.

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

문제

문제

출처

ICPC

메모리 초과 도와주세요

skesswswkk 3년 전 0

joonas 3년 전 1

skesswswkk 3년 전 0

skesswswkk 3년 전 0

joonas 3년 전 1

joonas 3년 전 1

skesswswkk 3년 전 1

skesswswkk 3년 전 1

joonas 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말