이 문제의 포인트는 주어지는 DNA의 조각 수(N)가 10 이하라는 것입니다. 이 말은 모든 조각이 배치될 수 있는 경우의 수가 10! = 3628800으로, 모든 경우를 다 살펴보아도 시간이 충분하리란 것을 알 수 있습니다.(일반적으로 1억정도를 문제 풀이의 시간한계로 잡으니까요.)
아래 첨부된 소스를 보시면 알겠지만, next_permutation 함수를 이용해서 string이 배치될 수 있는 모든 경우의 수를 다 만들어 보고, 각각 완성된 string에 대해서 이 스트링이 palindrome인지 아닌지를 판별해봅니다. 만약 palindrome이라면 그 중에서 사전순으로 가장 작은 string을 답으로 기억합니다.
실제 대회때 저는 이 문제에서 한번 WA를 받았었는데, 이는 제가 palindrome을 만족하는 string을 찾자마자 프로그램을 종료했기 때문입니다. 사전순으로 가장 처음에 있는 palindrome은 처음에 발견되는 string이 아니라 나중에 발견될 수도 있기 때문입니다.

[code c++]
#include
#include
#include
#include
using namespace std;
vector dat;
bool isPal(string&);
int main(void)
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
dat.resize(n);
for(int i=0;i>dat[i];
sort(dat.begin(), dat.end());
string ans="z";
ans[0]++;
do
{
string conc;
for(int i=0;i