[C/C++] 백준 1509: 팰린드롬 분할 (DP)
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 팰린드롬? 이 문제는 어떤 문자열을 팰린드롬으로 분할할 때 분할의 개수의 최솟값을 구해야하는 문제이다. 팰린드롬인지 아닌지는 10942: 팰린드롬? 문제와 같이 어떤 수가 팰린드롬일 때 양쪽끝(맨 처음과 맨 끝)을 제외한 가운데 부분도 팰린드롬이라는 사실을 이용하여 시간복잡도를 줄이며 확인할 수 있다. 그 과정은 아래 포스팅을 참..
2023. 10. 21.
