[백준] 13330 유사 팰린드롬

딱 DP 점화식이 나오는 문제인데, DP[i] = 0~i 까지 쎄타 팰린드롬을 만들때의 최소 개수라고 하자. j = 0 ~ i - 1 까지 검사해보며 [j + 1, i] 구간이 쎄타 팰린드롬이 된다면 DP[i] = min(DP[i], DP[j-1] + 1) 을 해줄 수 있다. 그럼 [j + 1, i] 구간이 쎄타 팰린드롬이 되는지를 O(1)에 알 수 있다면 O(N^2)(정확히는 O(N*(N-1)/2)) 에 DP를 때려버릴 수 있다. 어떻게 O(1)에 알 수 있을까? 몰라 그냥 3중 for문으로 돌렸더니 O(N^3)로 통과함 ㅅㄱ 라고 할뻔 가장 쉬운 방법은 메모리를 512MB 나 주므로 n^2 짜리 2차원 배열을 전처리해서 사용하는 방법이다. 맞힌사람들 중 메모리가 10만 이상인 사람들은 이걸 쓴 것이다. 나..........

원문링크 : [백준] 13330 유사 팰린드롬