[Boj 3080] 백준 - HERKABE (트라이, 정렬, 접두사)

https://www.acmicpc.net/problem/3080* 풀이 (트라이, 정렬, 접두사)i) 트라이에 모든 단어를 저장을 한다.ii) 가능한 경우의 수는 각 노드의 (output + NextCnt)!의 곱이다.output : 현재 노드에서 끝나는 단어가 있는지 판별 (0 또는 1)NextCnt : 자신 노드의 개수iii) 근데 모든 단어를 저장하게 되면 메모리초과가 된다.3000 * 3000 * 26 = 234,000,000의 공간을 잡아먹어서 터진다.output이 있는지 자식이 몇개인지만 알면 되는데 쓸모없는 노드까지 모두 저장해버려서 생기는 문제이다.우리는 공통 접두사에 대해 집중해볼 필요가 있다.먼저 두 번째 예제를 정렬하면 아래와 같다 MARAMARICAMARTAMARTINAMATOi번..........