Hoon222y

https://www.acmicpc.net/problem/1509 입력되어진 문자열을 팰린드롬들로 분할하였을 때 그 분할개수의 최소값을 출력하는 문제이다. 최소값을 구하는 문제라고 적혀있는 것처럼 DP로 접근을 해보자. dp 배열의 개념을 먼저 잡고 가자면 dp[i] 는 문자열 i번째 문자까지 갔을 떄 필요한 최소한의 팰린드롬 개수이다. 따라서 점화식을 새운다면 dp[i] = min(dp[j-1])+1 ( 여기서 i와 j는 팰린드롬 일 경우 )이 될 것이다. 따라서 먼저 i와 j가 팰린드롬인지를 판별하는 함수를 먼저 만들고 점화식대로 문제를 해결해나가면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445..