인코딩

대부분의 프로그래밍 언어에서 문자열 상수에는 키보드로 직접 입력할 수 없는 문자가 들어갈 수 있다. 보통 백슬래시 같은 특별한 표시(marker) 기호를 사용해 이를 표현하며, 문자열의 대부분은 그대로(verbatim) 읽히고 나머지는 어떤 방식으로 해석(interpreted) 된다.

P. Entropic 교수는 고정된 표시 기호를 쓰는 방식이 너무 경직되어 있다고 생각한다. 백슬래시가 아주 많이 들어간 문자열을 인코딩해야 한다면 어떻게 할 것인가? 그래서 그는 동적 인코딩(dynamic coding) 을 제안한다. 이 방식에서는 문자열의 그대로 읽는 부분과 해석하는 부분을 표시 기호로 명시적으로 구분하며, 그 표시 기호는 문자열 안에서 바뀔 수 있다.

인코딩된 문자열은 현재 모드(해석 모드 또는 그대로 모드)와 현재 표시 기호를 유지하며 왼쪽에서 오른쪽으로 해독한다. 처음에는 해석 모드이고 표시 기호는 정해져 있지 않다. 규칙은 다음과 같다.

• 해석 모드에서 같은 기호가 연속해서 두 번 나오면, 그 기호가 현재 표시 기호가 되고 그 두 글자는 아무 것도 출력하지 않고 소비된다. 이렇게 첫 표시 기호가 정해지고, 이후에도 같은 방식으로 표시 기호가 바뀐다.
• 현재 표시 기호가 한 번 나오면 해석 모드와 그대로 모드가 서로 전환되며, 아무 것도 출력하지 않는다.
• 그 밖의 기호는 정확히 한 글자를 출력한다. 해석 모드이면 대문자로, 그대로 모드이면 소문자 그대로 출력한다.

연속된 두 글자가 특별하게 취급되는 것은 해석 모드에서뿐이다. 그대로 모드에서는 같은 기호가 반복되어도 단순히 그대로 두 글자일 뿐이다.

예를 들어 알파벳이 $\{a, b, c\}$ 일 때, 인코딩된 문자열 cccabcabcaacbbcaac 는 abABaaCC 로 해독된다. 여기서 대문자 부분이 해석된 부분이고 소문자 부분은 그대로 읽은 부분이다.

Entropic 교수는 동적 인코딩이 공간 측면에서 얼마나 효율적인지 알고 싶어 한다. 그대로 읽을 부분은 소문자로, 해석할 부분은 대문자로 적힌 목표 문자열이 주어질 때, 그 문자열의 가장 짧은 인코딩의 길이를 구하여라.

첫째 줄에 정수 $k$ ($2 \le k \le 26$) 가 주어진다. 이는 알파벳의 크기이며, 알파벳은 영어 소문자 중 앞에서부터 $k$ 개의 문자로 이루어진다.

둘째 줄에 목표 문자열이 주어진다. 그대로 읽을 문자는 소문자로, 해석할 문자는 대문자로 적혀 있으며, 대소문자를 무시하면 모든 문자는 앞에서부터 $k$ 개의 문자 중 하나이다. 문자열의 길이는 최대 $100\,000$ 이다.

동적 인코딩 방식으로 주어진 문자열을 인코딩했을 때 가장 짧은 인코딩의 길이(글자 수)를 정수 하나로 출력한다.