시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1596 | 575 | 481 | 45.420% |
팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다.
만일 어떤 단어가 팰린드롬이 아니라면, 그 단어는 여러 개의 팰린드롬으로 나누어질 수 있을 것이다. 단어가 주어졌을 때 이를 여러 개의 팰린드롬으로 나누되, 나누어진 팰린드롬의 개수가 최소가 되도록 나누려고 한다.
예를 들어 abaccbcb라는 문자는 aba, cc, bcb와 같이 세 개의 문자열로 나누면 각각 팰린드롬이 된다. 하지만 두 개의 문자열로 나누어서는 결코 각각이 모두 팰린드롬이 될 수 없다. 따라서 이 경우의 답은 3이다. 마찬가지로 anavolimilana와 같은 문자열은 ana, v, o, limil, ana의 다섯 개의 문자열로 나누면 각각 팰린드롬으로 만들 수 있으며, 네 개로 나누어서는 각각이 모두 팰린드롬이 되도록 만들 수 없다. 따라서 이 경우의 답은 5이다.
문자열이 주어졌을 때, 이 문자열을 최소 개수의 팰린드롬으로 나누는 프로그램을 작성하시오. 문자열 자체가 팰린드롬이라면 굳이 나눌 필요는 없다.
첫째 줄에 단어가 입력으로 들어온다. 단어는 영어 소문자로만 이루어져 있으며, 그 길이는 2,000을 넘지 않는다.
주어진 문자열을 최소 개수의 팰린드롬으로 나누었을 때, 그 개수를 출력한다.
anaban
2
abaccbcb
3
anavolimilana
5