어떤 문자열에서 특정한 패턴이 반복될 경우, 이를 이용하여 문자열을 좀 더 짧게 나타낼 수도 있다. 이러한 방법을 압축 기법이라고 하는데, 문자열을 압축하기 위한 여러 가지 효율적인 방법들이 연구되었다. RLE(Run Length Encdoing) 방법은 이러한 압축 방법 중 가장 기초적인 방법이다. RLE는 문자열에서 어떤 문자가 반복될 경우, 이 문자를 한 번만 저장하고 그 대신 반복 회수를 저장하는 방법이다. 이를 이용하면 abccddd는 abc2d3와 같이 압축될 수 있다.

문자 대신 문자열을 이용하면 RLE를 좀 더 개선할 수 있다. 예를 들어 주어진 문자열에서 S라는 문자열이 k번 반복될 경우, 이를 k(S)와 같은 식으로 표현할 수 있다. 예를 들어 letsgogogo는 lets3(go)와 같이 압축될 수 있다. 이 경우 원래 문자열의 길이는 10이지만 압축된 문자열의 길이는 9가 된다. 압축된 문자열의 길이를 계산할 때에는 괄호와 k를 나타낼 때 필요한 길이도 포함해서 계산한다. 또, 압축을 중첩해서 할 수도 있는데, 예를 들어 nowletsgogogoletsgogogo는 now2(lets3(go))로, nowletsgogogoletsgogogoandrunrunrun 은 now2(lets3(go))and3(run)으로 압축될 수 있다. 이렇게 개선된 RLE방법에서 abc2d3로는 압축할 수 없고, ab2(c)3(d) 로만 압축할 수 있다.

문자열이 주어졌을 때, 이를 압축하는 방법은 여러 가지가 있을 수 있다. 그 중 가장 짧은 방법의 길이를 알아내는 프로그램을 작성하시오.

--------------------------

이거 문자를 압축해도 되고 안해도 되는거임?

그니까 가령 개선된 RLE의 경우 gg는 2(g)로 압축하는게 길이가 더 늘어나버리는데

개선된 RLE에서 압축하는게 손해면 압축하지 않는 것을 결정할 수 있어서 그 수많은 경우중 가장 효율적인 것을 찾는건지

아님 걍 RLE vs 개선된 RLE vs 원문 중 어떤 방법이 제일 효율적인지 찾는건지 몰겠네