반응형 pallindrome1 #1509 팰린드롬 분할 팰린드롬 분할은 주어진 문자열에 팰린드롬이 되는 단어들로 나눌 때 나오는 팰린드롬의 개수가 최소가 되는 수를 계산합니다. 맞힌 사람들의 수행시간을 보니, 제 알고리즘은 그다지 좋지는 않습니다. 제 알고리즘은 \(O(N^3)\)인데, 이보다 적게 계산할 수 있는 방법이 있겠죠. 일단 기본적인 생각은 앞에서부터 n개의 글자에 대한 팰린드롬 분할의 최소 개수를 구합니다. 이것을 \(dp_n\)이라고 한다면, 1개의 글자는 그 자체로 팰린드롬이니, \[ dp_0 = 0, dp_1 = 1 \] 이 됩니다. \[ dp_{n+1} = min_{i = 0,...,n-1}(dp_{i} + 1~ if~ s[i:n]~is~pallindrome) \] 이 방식대로 구현한 프로그램은 아래와 같습니다. 좀 더 효율적인 프로그램을.. 2022. 8. 22. 이전 1 다음 728x90