Palindrome > 문제은행

본문 바로가기


알고리즘 다이나믹2

1635 : Palindrome

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 7 회    시도횟수: 48 회   



뒤집어도 같은 말이 되는 단어를 팰린드롬(Palindrome)이라고 한다. N개의 서로 다른 영어 단어가 주어질 때 이를 이어 붙여 길이가 L인 팰린드롬을 모두 몇 가지 방법으로 만들 수 있는지 출력하는 프로그램을 작성하시오. 단, 하나의 단어를 중복해서 사용할 수 있으며, 서로 다른 조합이나 순서로 단어를 붙여 같은 팰린드롬을 만든 경우 다른 방법으로 간주한다.

 

예를 들어 N이 5, L이 4라고 하고 A, AA, BB, BC, CB 이렇게 5개의 영어 단어가 주어졌다고 하자. 이 경우 아래와 같이 총 9개의 방법으로 팰린드롬을 만들 수 있다.

 

A | A | A | A
AA | A | A
A | AA | A
A | A | AA
AA | AA
A | BB | A
BB | BB
BC | CB
CB | BC


첫째 줄에 N이, 둘째 줄에 L이 주어진다. N은 50이하의 자연수, L은 30이하의 자연수이다. 셋째 줄부터 N개의 줄에 한 줄에 하나씩 영문자 대문자로만 이루어진 길이가 15이하인 영어 단어가 주어진다. 주어지는 모든 영어 단어는 서로 다르다.


첫째 줄에 입력으로 주어진 단어를 이어 붙여 길이가 L인 팰린드롬을 만들 수 있는 방법의 수를 출력한다.
그 방법의 수는 21억을 넘지 않는다.

[Copy]
5
4
A
AA
BB
BC
CB
[Copy]
9





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.