목록Problem Solving/BOJ (92)

이동식 저장소

1509. 팰린드롬 분할

1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문자열을 팰린드롬인 부분 문자열로 나눠야 한다. solve(i)[i,len] 구간의 정답으로 정의하자. 이 값은 [i,len]이 팰린드롬이라면 1, 그렇지 않다면 minlenj=i(1+solve(j))이다. 물론 [i,j] 부분 문자열은 팰린드롬이어야 한다. 단, 중복 계산을 방지하기 위해 solve(i)의 값을 배열에 저장..

Problem Solving/BOJ 2020. 3. 29. 15:20