시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 616 | 108 | 76 | 29.572% |
지민이는 단어 N개를 가지고 있고, 이 단어를 이용해서 팰린드롬 문장을 몇 개 만들 수 있는지 알아보려고 한다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 0보다 크다. 문장은 단어로만 구성되어 있고, 각 단어의 사이에는 공백이 한 칸 있다. 문장의 길이는 0보다 커야 한다.
팰린드롬 문장은 공백을 무시했을 때, 앞에서부터 읽을 때와 뒤에서부터 읽을 때가 같은 것이다.
몇 개의 팰린드롬 문장을 몇 개 만들 수 있는 지 구해보자. 각 단어는 문장 내에서 최대 1번까지 사용할 수 있고, 두 문장이 공백을 무시했을 때 같아도, 생긴 형태가 다르면 서로 다른 문장이다. 예를 들어 “a ba”와 “ab a”는 다른 문장이다.
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 13)이 주어진다. 둘째 줄부터 N개의 줄에 각 단어가 주어진다. 각 단어의 길이는 최대 13이고, 중복되지 않는다.
첫째 줄에 단어를 이용해서 만들 수 있는 팰린드롬 문장의 개수를 출력한다.
2 a ba
2
3 ab bcd efg
0
3 a bba abb
7
10 aabccc ccbbca a acaabb aaa aab c babb aacaa b
47