palindrome
-
[BOJ] 1509 팰린드롬 분할PS/BOJ 2020. 7. 15. 18:42
https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하�� www.acmicpc.net 알고리즘: DP 시간복잡도: O(N^2) 접근: 1. 팰린드롬 문자열 -> 팰린드롬 문자는 부분 문제의 속성을 지녔기 때문에 Dynamic 으로 접근하기가 용이함. 2. (특정 규칙을 가지고) 분할 및 개수 구하기 -> 이 부분도 Dynamic 속성을 응용하기 쉽다. 예를 들어, D[i]: 0~i까지 분할(그룹)의 개수 라고 ..