ReMorse
시간 제한1초메모리 제한512 MB
메시지의 인코딩 총 길이가 최소가 되도록 각 알파벳에 모스 부호열을 새로 배정하고, 그 최솟값을 구한다.
문제
모스 부호는 점과 선 기호의 나열을 알파벳 문자에 대응시킨 것이다. 이 대응을 새로 정해서 주어진 메시지를 인코딩할 때 총 길이가 최소가 되도록 하고, 그 최소 총 길이를 구하라.
점 기호의 길이는 1이다. 선 기호의 길이는 3이다. 한 문자를 나타내는 부호들 사이의 간격은 1이다. 문자 부호 사이의 간격은 3이다. 공백, 구두점, 대소문자는 무시하므로, 다음 텍스트는
The quick brown dog jumps over the lazy fox.
다음과 같이 인코딩된 것으로 본다.
THEQUICKBROWNDOGJUMPSOVERTHELAZYFOX
예를 들어 입력 ICPC의 답은 17이다. 두 C를 점 하나로, I를 선 하나로, P를 점 두 개로 인코딩하면 다음과 같고
− ∙ ∙∙ ∙
길이는 (3) + 3 + (1) + 3 + (1 + 1 + 1) + 3 + (1) = 17이다.
입력
입력은 한 줄이며, 대문자 또는 소문자, 공백, 쉼표, 마침표, 느낌표, 물음표로 이루어진 문자열 s (1 ≤ |s| ≤ 32000)이다. 문자를 제외한 나머지는 모두 무시한다. 줄에는 문자가 적어도 하나 있다.
출력
모스 부호의 나열을 최적으로 새로 정했을 때 𝒔를 인코딩한 길이를 나타내는 정수 하나를 출력한다.