시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 140 45 37 39.785%

문제

어떤 문자열에서 특정한 패턴이 반복될 경우, 이를 이용하여 문자열을 좀 더 짧게 나타낼 수도 있다. 이러한 방법을 압축 기법이라고 하는데, 문자열을 압축하기 위한 여러 가지 효율적인 방법들이 연구되었다. 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

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Seoul 2005 J번

  • 빠진 조건을 찾은 사람: koosaga