종이 띠
면접 대비시간 제한2초메모리 제한512 MB
소문자로 이루어진 문자열을 최소한으로 잘라 그 조각들을 다시 배열했을 때 증가했다가 감소하는 바이토닉 문자열이 되도록 하는 자르기 횟수를 구합니다.
문제
Tito는 글자가 적힌 종이 띠를 받았다. 그는 이 글자들을 다시 배열하고 싶어 한다. 이를 위해 글자 사이를 원하는 횟수만큼 자른 뒤, 잘라 낸 종이 띠들을 다시 배열한다.
Tito는 정렬을 좋아하므로, 결과로 얻는 종이 띠가 bitonic이 되기를 원한다. 즉, 결과 문자열에서 어떤 위치를 골랐을 때, 그 위치까지(그 위치 포함) 앞쪽 문자들은 사전순으로 감소하지 않고, 그 위치부터(그 위치 포함) 뒤쪽 문자들은 사전순으로 증가하지 않아야 한다. 다음 예를 보자.
위 예의 결과 문자열은 bitonic이다. 첫 번째 e를 보자. aaabbe는 감소하지 않고, eeddcc는 증가하지 않는다. Tito는 이를 세 번의 자르기로 만들었다. 단조 문자열(계속 감소하지 않거나 계속 증가하지 않는 문자열)도 모두 bitonic이라는 점에 주목하라.
Tito가 문자열을 bitonic으로 만드는 데 필요한 최소 자르기 횟수를 구하라.
입력
각 입력은 하나의 테스트 케이스로 이루어진다. 프로그램은 서로 다른 입력에 대해 여러 번 실행될 수 있다.
각 테스트 케이스는 소문자로만 이루어진 문자열 ()가 적힌 한 줄로 주어진다. 이것이 Tito에게 주어진 종이 띠의 원래 문자열이다.
출력
필요한 자르기 횟수의 최솟값을 정수 하나로 출력한다.