algospot   10년 전

문제에서 보면 ABACABA의 분할 경우가 {A,B,A,C,A,B,A} / {ABA,C,ABA} / {A,BACAB,A} / {ABACABA} 이렇게 나와있는데 그럼 ABACABA에 대한 분할의 개수의 최솟값은 4란 말인가요?? ABACABA 같은 경우는 {ABA,C,A,B,A} 는 포함되지 않는건가요? 그리고 집합으로 생각해서 {ABA,C,A,B,A} 와 {A,B,A,C,ABA} 는 같은 경우로 보고 갯수를 더하면 안되는 건가요? 문제의 케이스 ABACABA의 경우 최소분할횟수는 문제에 있는 그대로 4개의 경우라고 생각하고 문제를 풀어야하는건가요?

chojl1125   10년 전

분할 집합 개수가 아니라 분할 집합 중 원소의 개수가 최소가 되는 집합을 찾으세요.
ABACABA 는 그 자체로 팰린드롬이므로 1개이고, 예제의 경우에는 {BB,C,DD,E,C,A,E,C,B,DABAD,D,C,E,B,A,CCC,B,D,C,A,ABDBA,DD} 로 22개네요.

댓글을 작성하려면 로그인해야 합니다.