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