시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 27 3 3 33.333%

문제

준규는 심심해서 팰린드롬 인코딩이라는 새로운 인코딩 방법을 만들었다. 

팰린드롬 인코딩은 0과 1로만 이루어진 자료만 인코딩 할 수 있으며, 다음과 같은 과정을 거친다.

  1. 문자열 S에서 짝수 길이인 팰린드롬 연속 부분 문자열을 찾는다. 팰린드롬은 앞에서부터 읽을 때와 뒤에서부터 읽을때가 똑같은 문자열을 말한다. 만약, 팰린드롬이 없는 경우에는 3단계로 간다.
  2. 찾은 팰린드롬 문자열 중에서 뒤의 절반을 지운다. 예를 들어, 찾은 문자열이 0110이면, 10을 지운다.
  3. 만약, 팰린드롬이 더 존재하면 다시 1단계로 돌아가고, 없으면 남은 문자열을 출력한다.

 

문자열 S가 주어졌을 때, 팰린드롬 인코딩을 했을 때, 나올 수 있는 결과 중에서 가장 짧은 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 1보다 크고, 10,000보다 작다.

출력

첫째 줄에 팰린드롬 인코딩을 했을 때 가능한 최소길이를 출력한다.

예제 입력

0111001

예제 출력

2

힌트

마지막 4개의 문자열 1001을 인코딩 한다. 그럼 01110이 된다. 여기서 다시 11을 인코딩 해서 0110을 만든다. 10을 지워서 마지막 문자열은 01이 된다.

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: protalk