[BOJ] #1509 팰린드롬 분할
시간 제한 메모리 제한 정답 비율 2 초 128 MB 46.610% 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제 해결 key point, '팰린드롬?' 문제를 활용, d[i]는 i번째까지 문자열의 팰린드롬 분할 최솟값. DP j번째 부터 i번째까지 팰린드롬인지 아닌지를 저장한 배열 c[j][i]를 활용해서 → 팰린드롬? 문제 활용 j~i까지의 문자열이 팰린드롬이라면 → c[j][i] == true d[i]는 d[j - 1] + 1이다..
2021. 2. 9.
