글 읽기 - 메모리 초과...

staphaniek 7년 전 0

트라이를 만들어서 bfs로 자식 수를 센 후 팩토리얼 곱을 하는 형식으로 풀었는데요

메모리 초과가 나네요... 노드 개수에 대한 관념이 없어서인지 모르겠는데

혹시 더 최적화 할 수 있는 방법이 있다면 힌트를 주실 수 있을까요...?

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define inf 1000000007

struct trie {
	trie* next[27] = { 0, };
};

int N;
char A[3005];
queue<trie*> Q;

long long int bfs(trie *now) {
	long long int ans = 1;
	Q.push(now);
	while (!Q.empty()) {
		trie* pos = Q.front(); Q.pop();
		int cnt = 0;
		for (int i = 0; i < 27; i++) {
			if (pos->next[i] != NULL) {
				if(i!=26)Q.push(pos->next[i]);
				cnt++;
			}
		}
		while (cnt > 0) {
			ans *= cnt;
			ans %= inf;
			cnt--;
		}
	}
	return ans;
}

int main() {
	scanf("%d ", &N);
	trie root;
	for (int i = 0; i < N; i++) {
		scanf("%s", A);
		trie *tmp = &root;
		for (int j = 0; j < strlen(A); j++) {
			if (tmp->next[A[j] - 'A'] == NULL) {
				tmp->next[A[j] - 'A'] =new trie();
				tmp = tmp->next[A[j] - 'A'];
			}
			else tmp = tmp->next[A[j] - 'A'];
		}
		tmp->next[26] = new trie();
	}
	printf("%lld\n", bfs(&root));
	return 0;
}

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

문제

문제

출처

ICPC

메모리 초과...

staphaniek 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말