페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4778

Vim 2s 512MB

문제

석표는 요즘 소설을 쓰고 있다.

그것도 무려 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


출처

BOI 2013

로그인해야 코드를 작성할 수 있어요.