qoaqkqh   1달 전

음절이 시작과 끝이 같은 문자열을 최소의 개수로 분리하는 문제인데요

혹시 푸신분 어떤식으로 푸셨는지 설명해주실수있나요~?

appa   1달 전

KMP N번 수행해서 O(N^2) DP를 했던 것 같네요.

qoaqkqh   1달 전

문자열 최대길이는 5000이였나요~?

좀더 자세히 설명해주시면 감사하겠습니다 .. 

appa   1달 전

D(i)를 1~i번째 문자열에 대한 답이라고 하면, D(i) = min(D(j) + F(j+1 ~ i)) (j < i)였나 이런식이었던 것 같아요.

F(j+1 ~ i)는 문자열 S(j+1 ~ i)의 prefix와 suffix가 같은 길이를 L이라 했을 때에 L이 조건을 만족하면 1, 아니면 0이었나... 아니면 L자체였나...

문제 자체가 잘 기억이 안나지만 대충 이런 식이었던 것 같아요.

appa   1달 전

저 F를 계산을 미리 해두기 위해서 S(1~N)에 대해 KMP의 Pi배열을 구해놓고, S(2~N)에 대해 Pi 배열을 구해놓고, .... N번 KMP 돌렸어요.

qoaqkqh   1달 전

답변 감사합니다.

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