3개의 댓글이 있습니다.
-
-
hyunhwan -
그럴 필요 없이 해당 문제의 경우 O(N^3) + 적적한 커팅으로 AC를 받을 수 있긴 합니다 :)
예전에 다음과 같이 editorial이 올라와 있습니다. 참고하시길 바랍니다.
http://algospot.com/discussion/166
12년 전 link
-
-
-
safariworld -
그 editorial을 보고 다른 풀이로는 전부 풀어봐서 이번에 suffix tree로 풀어보려고 하고 있습니다. ㅠ_ㅠ
suffix tree를 linear하게 구하는 방법이라.. 좀더 생각해보겠습니다 ㅎㅎ
12년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
safariworld
안녕하세요. 여기에 처음 글을 써보는 safari라고 합니다.
이 문제를 suffix tree를 써서 풀어보려고 하는데요
트리를 O(n^2) 시간복잡도로 구현했고 여기서 dfs돌면서 답을 구했습니다.
그런데 suffix tree을 공간복잡도가 O(n^2)으로 구현해서 메모리가 터집니다. ㅜㅜ(5000*5000이라 초기화할때 터집니다 ㅠ.ㅠ)
문제 링크:[http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=283&page=show_problem&problem=1902]
어떻게 해야할까요 ㅠ,ㅠ
12년 전