흙금이네 블로그

아이디어 부분 문자열들의 팰린드롬 여부를 확인하고 동적 계획법으로 분할 최소 개수를 구해 나간다. 풀이 #1 S의 길이를 N에 저장하고, S의 부분 문자열이 팰린드롬인지 여부를 저장하기 위한 2차원 리스트 is_pal을 만든다. is_pal[i][j]는 문자열 S의 인덱스 i부터 인덱스 j까지의 부분 문자열이 팰린드롬이면 1, 그렇지 않으면 0을 나타낸다. 팰린드롬 분할 최소 개수를 저장하기 위해 0으로 채워진 N+1 길이의 리스트 dp를 만든다. 이후 코드상 인덱스 에러 방지를 위해 문자열 S에서 인덱스 j까지의 팰린드롬 분할 최소 개수는 dp[j+1]에 저장한다. for문은 1부터 시작하므로 is_pal[0][0]과 dp[1]은 for문 실행 전에 저장한다. 길이가 1인 부분 문자열과 바로 앞의 문자..