시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 514 | 167 | 120 | 37.500% |
어떤 문자열에서 특정한 패턴이 반복될 경우, 이를 이용하여 문자열을 좀 더 짧게 나타낼 수도 있다. 이러한 방법을 압축 기법이라고 하는데, 문자열을 압축하기 위한 여러 가지 효율적인 방법들이 연구되었다. 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)
로만 압축할 수 있다.
문자열이 주어졌을 때, 이를 압축하는 방법은 여러 가지가 있을 수 있다. 그 중 가장 짧은 방법의 길이를 알아내는 프로그램을 작성하시오.
첫째 줄에 알파벳 소문자로 이루어진 문자열이 주어진다. 문자열의 길이는 200자를 넘지 않으며 공백 없이 주어진다.
첫째 줄에 최소 길이를 출력한다. 압축하지 않는 경우가 더 짧은 경우에는 원래 문자열의 길이를 출력한다.
letsgogogo
9
abc
3
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Seoul 2005 J번