글 읽기 - 메모리 초과가 어디서 나는지 모르겠습니다

minu0122 5년 전 0

아래의 코드는 입력을 다 받은 뒤 y축과 x축을 크기순으로 정렬하고 그 값들을 val이라는 벡터에 2차원으로 넣어준다음 각 점들에 대해서 최대 6개의 인접한 점들을 보고 최솟값을 출력하는 프로그램인데 계속 메모리 초과가 납니다. 혹시 어디서 메모리 초과가 나고 어떻게 계산해야 그런 경우도 계산 할 수 있는지 알려주실 수 있나요?

#include <iostream>
#include <vector>

using namespace std;

int point[100000][2];
int buff[100000][2];
int check[20001];
vector<vector<int>> val;
vector<int> tmp;
int n, buf, buf1, buf2, m = 1000000000, size1, size2, i, j, p;
int upper(vector<int> a, int num, int start, int end);
int lower(vector<int> a, int num, int start, int end);
void u();
void d();
void l();
void r();
void closest();

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (i = 0; i < 20001; i++)
		check[i] = 0;
	for (i = 0; i < n; i++)
	{
		cin >> point[i][0] >> point[i][1];
		check[point[i][1] + 10000]++;
	}
	for (i = 1; i < 20001; i++)
		check[i] += check[i - 1];
	for (i = 0; i < n; i++)
	{
		buf = point[i][1] + 10000;
		check[buf]--;
		buff[check[buf]][0] = point[i][0];
		buff[check[buf]][1] = point[i][1];
	}
	for (i = 0; i < 20001; i++)
		check[i] = 0;
	for (i = 0; i < n; i++)
		check[buff[i][0] + 10000]++;
	for (i = 1; i < 20001; i++)
		check[i] += check[i - 1];
	for (i = n - 1; i >= 0; i--)
	{
		buf = buff[i][0] + 10000;
		check[buf]--;
		point[check[buf]][0] = buff[i][0];
		point[check[buf]][1] = buff[i][1];
		buf = buff[i][0];
	}
    //여기까지 정렬 x값이 같으면 y값이 큰것이 더 뒤로 감
	tmp.push_back(point[0][0]);
	tmp.push_back(point[0][1]);
	for (i = 1; i < n; i++)
	{
		if (point[i][0] != point[i - 1][0])
		{
			val.push_back(tmp);
			tmp.clear();
			tmp.push_back(point[i][0]);
			tmp.push_back(point[i][1]);
		}
		else
			tmp.push_back(point[i][1]);
	}
	val.push_back(tmp);
    //val에 x값을 넣고 그 x값에 해당하는 y값을 크기순으로 넣어줌
	size1 = val.size();
	for (i = 0; i < size1; i++)
	{
		size2 = val[i].size();
		for (j = 1; j < size2; j++)
			closest();//한 점에서 위, 아래, 왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래의 점을 보고 거리를 계산함
	}
	cout << m;
}

int upper(vector<int> a, int num, int start, int end)
{
	if (start > end)
		return a[start];
	p = start + end;
	p >>= 1;
	if (a[p] == num)
		return num;
	else if (a[p] > num)
		return upper(a, num, start, p);
	else
		return upper(a, num, p + 1, end);
}

int lower(vector<int> a, int num, int start, int end)
{
	if (start == end)
		return a[start];
	p = start + end;
	p >>= 1;
	if (a[p] == num)
		return num;
	else if (a[p] > num)
		return lower(a, num, start, p - 1);
	else
		return lower(a, num, p, end);
}

void u()
{
	buf = val[i][j + 1] - val[i][j];
	buf *= buf;
	if (m > buf)
		m = buf;
}

void d()
{
	buf = val[i][j] - val[i][j - 1];
	buf *= buf;
	if (m > buf)
		m = buf;
}

void l()
{
	buf = val[i][0] - val[i - 1][0];
	buf *= buf;
	buf1 = upper(val[i - 1], val[i][j], 1, val[i - 1].size()) - val[i][j];
	buf1 *= buf1;
	buf2 = lower(val[i - 1], val[i][j], 1, val[i - 1].size()) - val[i][j];
	buf2 *= buf2;
	if (m > buf + buf1)
		m = buf + buf1;
	if (m > buf + buf2)
		m = buf + buf2;
}

void r()
{
	buf = val[i + 1][0] - val[i][0];
	buf *= buf;
	buf1 = upper(val[i + 1], val[i][j], 1, val[i + 1].size()) - val[i][j];
	buf1 *= buf1;
	buf2 = lower(val[i + 1], val[i][j], 1, val[i + 1].size()) - val[i][j];
	buf2 *= buf2;
	if (m > buf + buf1)
		m = buf + buf1;
	if (m > buf + buf2)
		m = buf + buf2;
}

void closest()
{
	if (j < size2 - 1)
		u();
	if (j > 1)
		d();
	if (i > 0)
		l();
	if (i < size1 - 1)
		r();
}

minu0122 5년 전 0

생각도 못한 부분이네요..정말 감사합니다!

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

문제

문제

출처

ICPC

메모리 초과가 어디서 나는지 모르겠습니다

minu0122 5년 전 0

minu0122 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말