시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 394 125 97 38.492%

문제

팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다.

만일 어떤 단어가 팰린드롬이 아니라면, 그 단어는 여러 개의 팰린드롬으로 나누어질 수 있을 것이다. 단어가 주어졌을 때 이를 여러 개의 팰린드롬으로 나누되, 나누어진 팰린드롬의 개수가 최소가 되도록 나누려고 한다.

예를 들어 abaccbcb라는 문자는 aba, cc, bcb와 같이 세 개의 문자열로 나누면 각각 팰린드롬이 된다. 하지만 두 개의 문자열로 나누어서는 결코 각각이 모두 팰린드롬이 될 수 없다. 따라서 이 경우의 답은 3이다. 마찬가지로 anavolimilana와 같은 문자열은 ana, v, o, limil, ana의 다섯 개의 문자열로 나누면 각각 팰린드롬으로 만들 수 있으며, 네 개로 나누어서는 각각이 모두 팰린드롬이 되도록 만들 수 없다. 따라서 이 경우의 답은 5이다.

문자열이 주어졌을 때, 이 문자열을 최소 개수의 팰린드롬으로 나누는 프로그램을 작성하시오. 문자열 자체가 팰린드롬이라면 굳이 나눌 필요는 없다.

입력

첫째 줄에 단어가 입력으로 들어온다. 단어는 영어 소문자로만 이루어져 있으며, 그 길이는 2,000을 넘지 않는다.

출력

주어진 문자열을 최소 개수의 팰린드롬으로 나누었을 때, 그 개수를 출력한다.

예제 입력

anavolimilana

예제 출력

5

힌트