| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 300 | 167 | 140 | 59.322% |
Albert는 QWERTY 키보드를 이용해 (위 그림 참고) 영문 대문자로 ('A'-'Z') 구성된 문자열을 입력하고 싶다. 아직 키보드 만지는 것이 서툰 Albert는 왼쪽 검지만을 이용해 버튼을 누르는 버릇이 있다.
각 버튼을 눌렀다 떼어서 글자 하나를 입력하는데 1초가 걸리고, 검지를 한 버튼에서 인접한 다른 버튼으로 옮기는데는 2초가 걸린다고 하자 (문자열을 입력하는 동안 손가락은 항상 키보드 버튼 위에서만 이동한다고 하자).
각 버튼의 주변에는 최대 6개의 인접한 버튼이 있을 수 있다. 가령, 검지를 S버튼에서 A, W, E, D, X, 혹은 Z로 옮기는 경우 2초가 걸린다.
Albert가 어떤 문자열을 입력하기 위해서는 먼저 왼쪽 검지를 해당 문자열의 첫 글자에 해당하는 버튼 위에 올린 후, 그 때 부터 시간을 측정한다.
만약 "QWERTY" 라는 문자열를 입력하려고 한다면, 아래와 같은 방법으로 16초만에 입력할 수 있다.
다른 예로, "LOM" 라는 문자열을 입력하려 한다면 9초가 걸린다.
입력으로 영문 대문자('A"-'Z')로만 구성된 문자열이 주어졌을 때, Albert가 가장 빨리 입력할 경우 몇 초나 필요한지 계산하는 프로그램을 작성하시오.
입력 첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 한 줄에 걸쳐 영문 대문자로만 구성된 문자열이 (공백없이) 주어진다.
각 테스트 케이스에 대하여 입력으로 주어진 문자열을 입력하는데 걸리는 최소 시간을 출력한다.
5 QWERTY LOM FFGGFF VGTRDCF MPML
16 9 10 19 20
케이스 1: 본문에서 다루었다.
케이스 2: 본문에서 다루었다.
케이스 3: F를 두 번 연속 누르는데 2초, F에서 G로 이동하는데 2초, G를 두 번 누르는데 2초, F로 다시 이동하는데 2초, F를 두 번 누르는데 2초가 걸려 총 10초가 걸린다.
케이스 4: 각 문자열의 글자를 누르는데 1초씩 걸리고 (총 7초), 연속한 문자열 두 개는 모두 인접한 버튼이므로 이동하는데 6*2=12초가 걸려서 총 19초가 걸린다.
케이스 5: M에서 P혹은 P에서 M으로 이동하는데 각 6초가 걸리고 M에서 L로 이동하는데 4초가 걸린다. 버튼을 누르는 시간까지 포함하여 총 20초가 걸린다.