시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 203 | 74 | 44 | 61.111% |
팰린드롬이란 왼쪽에서부터 읽을 때와 오른쪽에서부터 읽을 때가 같은 문자열을 말한다. 이때, 공백은 무시한다.
N개의 단어가 주어진다. 이 단어를 이용해서 문자열 S를 만들 수 있다. 단어와 단어 사이에는 공백을 하나 집어 넣어야 하며, 각 단어를 여러 번 사용하거나, 사용하지 않는 단어가 있어도 된다. 같은 단어를 연속해서 사용하는 경우에도 공백을 집어넣어야 한다.
이렇게 만들 수 있는 문자열 S중에서 팰린드롬이면서, 길이가 K이하인 것의 개수를 구하는 프로그램을 작성하시오. 빈 문자열은 팰린드롬이 아니다. 문자열의 길이는 공백을 포함한다. S는 공백으로 시작하거나 끝날 수 없다.
첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같고, K는 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 주어진다. 알파벳 소문자로만 구성되어져 있고, 길이는 최대 15이며, 중복되지 않는다.
첫째 줄에 문제의 정답을 835454957로 나눈 나머지를 출력한다.
2 4 z zz
5
7 70 aba acaba baca cac b c a
370786966
1 100 hello
0
2 24 tragic cigar
1
예제 1의 경우에 만들 수 있는 단어는 다음과 같다.
z zz zz z z zz z z