글 읽기 - map 메모리관련 질문입니다.

jh20s 6년 전 0

D1: 1, D2:2000 일때 최대 관중석의 개수는 1216588입니다.

pair<int,int> 로 구성된 map에 최대 1216588개를 삽입하는데

64MB에서 메모리 초과가 뜹니다.

이게 왜 메모리 초과인지 모르겠습니다 ㅠㅠ

map에 대한 이해도가 적어서 그런데,

map에 들어가는 노드 하나당 메모리가 몇인가요?

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include<tuple>
#include<functional>
#include<utility>
#include<set>
#define inf 1000500000
using namespace std;

typedef pair<int, int> Pair;
typedef pair<Pair, int> PPair;


int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a%b);
}


int main(void) {
	int l, r;
	scanf("%d %d", &l, &r);

	map<Pair, int> ans;
	for (int i = l; i <= r; i++) {
		for (int j = 1; j <=i; j++) {
			int c = gcd(i, j);
			if (ans.find({ i / c,j / c })==ans.end())
				ans[{i / c, j / c}] = 1;
		}
	}
	printf("%d", ans.size());
}

chogahui05 6년 전 1

그건 정확히 잘 모르겠는데요.

일단 map 자체가 레드 블랙 트리로 구성되어 있으니까.. 자손 2개 정보까지 들어가야 하지 않을까 싶습니다.

트리 특성상 이 2개는 들어가고요. 거기에 추가적인 정보까지 (얼만큼 노드가 깊어졌나.. 등등) 들어가면.. 사실 무시 못합니다.

관심 있으시면 레드 블랙 트리 한 번 검색해 보세요.

진짜 진짜 재수가 없는 경우에는 메모리 초과 날 만하죠.

이 문제는 2차원 배열로 충분히 커버 가능합니다.

jh20s 6년 전 0

문제는 비슷한 방법으로 해결했지만,

map의 한 개의 노드에 몇 개의 변수가 들어가는지 찾아보려고 하는데, c++reference에서도 딱히 정보가 없어서 못 찾고 있어요 ㅠㅠ...

적어도 하나의 노드당 포인터나 변수가 5개 이상인것 같아 말해주신것 처럼 메모리 초과가 나는 것 같네요.

정확히 찾아보고 싶은데 좀 더 검색을 해봐야겠네요 ㅠ

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

문제

문제

출처

ICPC

map 메모리관련 질문입니다.

jh20s 6년 전 0

chogahui05 6년 전 1

jh20s 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말