문제
석표는 요즘 소설을 쓰고 있다.
그것도 무려 a부터 j까지 처음 10개의 알파벳만 가지고 소설을 쓰고 있다.
석표는 열심히 소설을 쓰고 있었지만 어느 날, 석표의 e키는 고장나고 말았다.
더 이상 e를 쓰지 못하면 중간부터 사용하는 글자의 종류가 줄어 소설이 어색해지고 말 것이다.
고민하던 석표는 지금까지 소설에 쓴 모든 e를 없애는 것이 해결책이라고 생각했다.
석표는 소설을 Vim으로 쓴다.
Vim은 여러 단축키가 있는 텍스트 에디터이다.
석표는 다음의 세 가지 단축키를 사용해 e를 모두 지울 것이다.
- x : x를 누르면 커서가 있는 위치의 글자가 사라진다.
- h : h를 누르면 커서가 왼쪽으로 한 칸 이동한다.
- f* : f를 누르고 *자리에 하나의 알파벳을 입력하면 커서 오른쪽에서 첫번째로 나오는 *로 커서가 이동한다.
단 e키가 고장난 것이므로 fe는 쓸 수 없다.
예를 들어 abce(a)bc가 현재 상태일때, (괄호는 커서)
h를 누르면 abc(e)abc,
x를 누르면 abc(a)bc,
fc를 누르면 abcab(c)가 된다.
석표는 위의 세 명령어를 사용해 최소한의 키 입력으로 모든 e만을 지우려고 한다.
맨 처음에는 커서가 첫 번째 위치에 있으며 소설의 맨 앞과 뒤에는 e가 없다.
e이외에 다른 글자를 지워서는 안되며 f* 명령은 두 번의 키 입력으로 센다.
모든 e를 지우려면 최소 몇 번의 입력이 필요할까?
입력
첫 줄에 소설의 길이 N이 주어진다.
둘째 줄에 소설의 내용이 주어진다.
1 <= N <= 70000
N<=500인 경우를 해결하면 50%의 점수를 받을 수 있다.
N<=5000인 경우까지 해결하면 추가적으로 10%의 점수를 받을 수 있다.
출력
첫째 줄에 모든 e를 지우기 위해 필요한 최소 키 입력의 수를 출력하라.
예제
35
chefeddiefedjeffeachbigagedegghehad
36