Dynamic Input Tool
시간 제한2초메모리 제한512 MB
빈 문자열에서 시작해 문자 하나를 덧붙이거나 현재 문자열의 비어 있지 않은 부분 수열을 덧붙이는 연산만으로 주어진 문자열을 만들 때 필요한 최소 연산 횟수를 구한다.
문제
CodingSlave 1.0은 새로운 텍스트 편집기이다. CodingSlave 1.0에서 문자열을 만들 때 사용할 수 있는 연산은 두 가지이다:
- 현재 문자열의 끝에 문자 하나를 추가한다.
- 현재 문자열의 비어 있지 않은 부분 수열을 골라 현재 문자열의 끝에 추가한다.
처음에는 현재 문자열이 비어 있다.
영소문자로 이루어진 단어가 주어졌을 때, 이 문자열을 만드는 데 필요한 최소 연산 횟수를 구하라.
입력
첫째 줄에 영소문자로 이루어진 문자열 가 주어진다 ().
출력
CodingSlave 1.0으로 를 만들기 위해 필요한 최소 연산 횟수를 한 정수로 출력한다.