글 읽기 - 트라이를 이용하여 풀었는데 메모리초과가 납니다.

jason9319 7년 전 0

알파벳을 트라이에 전부 삽입해준 후

Fac(자식의 수)를 전부 곱해주는 방법으로 풀었는데 메모리 초과에 걸립니다. 혹시 좀 더 효율적으로 문제를 해결할 수 있는 방법이 있을까요?

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 3000
#define MOD 1000000007
using namespace std;
long long r;
int n;
char a[MAX_N + 1];
long long fac(long long v) {
	if (v == 1)return 1;
	return (v*fac(v - 1)) % MOD;
}
struct Trie {
	Trie* next[27];
	int child;
	Trie() : child(0) {
		memset(next, 0, sizeof(next));
	}
	~Trie() {
		for (int i = 0; i < 27; i++) {
			if (next[i])
				delete next[i];
		}
	}
	void insert(const char* key) {
		if (*key == '\0') {
			if (next[26] == NULL)
				child++;
		}
		else {
			int curr = *key - 'A';
			if (next[curr] == NULL) {
				next[curr] = new Trie();
				child++;
			}
			next[curr]->insert(key + 1);
		}
	}
	void find(Trie* t) {
		if (t->child)
			r = r*fac(t->child) % MOD;
		for (int i = 0; i < 27; i++) {
			if (t->next[i])
				find(t->next[i]);
		}
	}
};
int main() {
	scanf("%d", &n);
	r = 1;
	Trie *root = new Trie;
	getchar();
	for (int i = 0; i < n; i++) {
		scanf("%s", &a);
		root->insert(a);
	}
	root->find(root);
	printf("%lld", r);
	return 0;
}

shjgkwo 7년 전 3

이 문제는 무작정 트라이를 구성하면 메모리 오버플로가 날 수 밖에 없습니다.

그래서 방법은 여러가지가 있는데 제가 쓴 방법은 좀 무식하지만

정렬했을 때, i, i+1간에 프리픽스 부분이 얼마나 일치하는가만 중요하기 때문에

그 부분을 제외한 나머지 부분은 커트하고 그거로 트라이를 구축했습니다.

일단은 제 풀이로 해보시고, 다른분들 풀이도 봐보세요 :)

jason9319 7년 전 0

감사합니다. 참고하겠습니다^^

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

문제

문제

출처

ICPC

트라이를 이용하여 풀었는데 메모리초과가 납니다.

jason9319 7년 전 0

shjgkwo 7년 전 3

jason9319 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말