RLE 압축

RLE(반복 길이 부호화, run-length encoding)는 같은 문자가 길게 반복되는 수열을 압축하는 간단한 방법이다. 어떤 수열을 부호화하면 그 수열의 코드를 얻는다. 핵심 아이디어는 같은 문자가 연속으로 나오는 구간(예: aaaaa)을, 어떤 문자가 몇 번 반복되는지를 나타내는 정보로 바꾸는 것이다.

크기가 n인 알파벳을 정수 집합 Sigma = {0, 1, ..., n - 1}로 나타낸다. 수열과 그 코드는 모두 Sigma 위의 문자열이다. 부호화에는 반복 표시(repetition mark)라고 부르는 특별한 문자가 쓰이며, 이 문자 역시 Sigma의 한 원소로서 e로 나타낸다. 처음에는 e = 0이지만, 코드를 읽는 도중에 바뀔 수 있다.

코드는 왼쪽에서 오른쪽으로 다음과 같이 해석한다. e를 현재의 반복 표시라고 하자.

• e와 다른 문자 a는 그 자체(문자 a 하나)를 의미한다.
• 현재의 반복 표시 e가 나오면, 바로 뒤의 두 문자 x, y가 e와 함께 하나의 묶음을 이루며, 다음 세 경우 중 정확히 하나로 해석된다.
  • x = e이면 묶음 (e, e, y)는 e를 y + 1개 나열한 것을 뜻한다.
  • 그렇지 않고 y = 0이면, x != e인 묶음 (e, x, 0)은 그 지점 이후로 반복 표시를 x로 바꾸며, 아무 문자도 출력하지 않는다.
  • 그렇지 않으면(x != e이고 y > 0), 묶음 (e, x, y)는 x를 y + 3개 나열한 것을 뜻한다.

반복 표시는 가운데 경우에서만 바뀌며, 나머지 두 경우에서는 그대로 유지된다.

예를 들어 n = 4라고 하자. 수열 1 0 0 2 2 2 2 2 2 3 3 3 3 3 0 3 0 2 0 0 0 0은 1 0 0 1 0 2 3 0 3 2 0 1 0 0 3 0 2 1 0 1로 부호화할 수 있다. e = 0으로 이 코드를 읽으면, 맨 앞의 1은 그 자체를 뜻하고, 0 0 1은 0 0을, 0 2 3은 2 여섯 개를, 0 3 2는 3 다섯 개를 만든다. 0 1 0은 반복 표시를 1로 바꾸고, 이어지는 0 3 0 2는 각각 그 자체를 뜻하며, 마지막의 1 0 1은(이제 반복 표시가 1이므로) 0 네 개를 만든다.

같은 수열도 여러 가지 방법으로 부호화할 수 있고, 코드마다 길이가 다를 수 있다. 코드 하나가 주어질 때, 그 코드가 나타내는 수열과 똑같이 해석되는 가장 짧은 코드의 길이를 구하여라.

알파벳의 크기와 코드를 읽어, 코드를 해석해 수열을 얻은 뒤, 그 수열로 해석되는 가장 짧은 코드의 길이를 출력하는 프로그램을 작성하여라.

첫째 줄에 알파벳의 크기를 나타내는 정수 n(2 <= n <= 30)이 주어진다. 둘째 줄에 코드의 길이를 나타내는 정수 m(1 <= m <= 100)이 주어진다. 셋째 줄에 어떤 수열의 코드를 이루는, 집합 {0, 1, ..., n - 1}에 속하는 정수 m개가 공백 하나로 구분되어 주어진다.

주어진 코드와 똑같은 수열로 해석되는 코드가 가질 수 있는 문자 개수의 최솟값을 정수 하나로 출력한다.