R00208
데이터 압축 분할
골드 III레이팅
의견: 0
설명
문자열 \(S\) 를 여러 개의 연속한 조각으로 나누어 압축하려 합니다. 압축 알고리즘의 특성상 각 조각은 회문(앞뒤로 읽어도 같은 문자열) 이어야 합니다.
조각으로 나누기 위해 자르는 횟수(컷의 개수)를 최소화하고 싶습니다. 예를 들어 길이 \(L\) 인 문자열을 \(t\) 개의 조각으로 나누면 컷은 \(t-1\) 번입니다.
모든 조각이 회문이 되도록 하는 최소 컷 횟수를 구하세요. 문자열 전체가 이미 회문이면 컷은 \(0\) 입니다.
제약
\(1 \le |S| \le 1000\)
입력 형식
한 줄에 소문자 알파벳으로 이루어진 문자열 \(S\) 가 주어집니다. (\(1 \le |S| \le 1000\))
출력 형식
모든 조각이 회문이 되게 하는 최소 컷 횟수를 출력합니다.
예제 1
입력
aab
출력
1설명
"aa" 와 "b" 로 나누면 두 조각 모두 회문이고 컷은 1번이면 됩니다.
예제 2
입력
abba
출력
0설명
"abba" 자체가 회문이므로 컷이 필요 없어 0 을 출력합니다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
데이터 압축 분할
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
데이터 압축 분할
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기