가상 키보드 입력 timer 4s memory 256MB

아래 그림과 같은 가상 키보드와 조정 버튼을 생각해보자. 그림의 왼쪽 부분은 가상 키보드이고 오른쪽 부분은 실제 키보드 버튼이다.

사용자가 텍스트를 입력하기 위해서는 가상 키보드의 키를 직접 누르는 대신에 실제 키보드 버튼을 이용해야 한다. 가상 키보드에는 "커서"가 있는데, 처음에는 커서가 왼쪽 맨 위 키의 위치에 있다. 우리는 실제 키보드에 있는 네 개의 화살표 버튼을 눌러서 커서를 움직일 수 있다. 화살표를 한 번 누르면 다른 글자가 나올 때까지 그 방향으로 이동하지만, 그런 글자가 없으면 이동하지 않는다. 커서가 적절한 키 위에 있을 때 실제 키보드의 선택(SEL) 버튼을 누르면 해당 문자가 선택되고 텍스트의 끝에 추가된다. 이러한 방식으로 주어진 텍스트의 문자들을 입력할 수 있으며 텍스트를 종료하려면 사용자가 Enter 키를 찾아 선택해야 (즉, 선택 버튼을 눌러야) 한다.

그림 1. 가상 키보드와 실제 키보드의 예시

입력 예 1에서 주어진 가상 키보드에서 CONTEST라는 텍스트를 입력하는 방법 중 하나로는 위 그림에서 빨간색으로 표시한 부분이 있다. 그림에서 붉은색 화살표는 이동한 것을 나타내며, ●은 SEL키를 누른 것을 의미한다. CONTEST를 입력하기 위해 실제 키보드 버튼을 30번 눌렀다는 것을 알 수 있다.

가상 키보드 레이아웃과 목표 텍스트가 주어지면, 텍스트를 입력하기 위해 실제 키보드 버튼을 최소 몇 번 눌러야 하는 지 구하여라.