4672. 수진이의 팰린드롬(D4)

수학의 세계는 신기하다는 것을 다시 한번 느끼게 해준 문제이다.

이 문제는 주어진 문자열을 재구성하여, 재구성한 문자열의 부분 문자열중 팰린드롬의 수가 최대일 때, 몇개인지를 계산하는 문제이다.

주어진 abcabc는 abccba로 재구성하면 a, b, c, c, b, a, cc, bccb, abccba로 9개가 나온다.

이 뿐만 아니라 acbbca, cbaabc등으로도 재구성 할 수 있다.

처음에는 문자열 길이가 최대 10글자이니 모든 문자열을 재구성해서 구현해보았더니 당연히 시간초과이다.

신기한건 문자 a가 10개로 구성된 aaaaaaaaaa은 답이 금방 나오는데 abvcfascdf 이렇게 문자가 섞이면 답이 나오는데 오래 걸렸다.

그래서 다른사람들은 어떻게 해결했는지 찾아보았는데, 이 문제의 경우의 수를 따져서 해결했다.

앞서 abccba는 여러가지 방법으로 최대 9개가 나왔다. 이중 aabbcc 이렇게 같은 문자열을 순서대로 배치했을 때, a, a, b, b, c, c, aa, bb, cc로 똑같이 최대 9개의 팰린드롬 부분 문자열을 가지게 된다.

(뭔가 수학적으로 증명해야 할 것 같지만.. 정확한 증명은 다른 고수분들이 해주실 것이다)

그러므로 각 알파벳을 이용하여 만드는 부분 팰린드롬을 계산해주면 PASS를 받을 수 있다.

#include <stdio.h>
#include <string.h>
 
int main(void)
{
    int T;
    setbuf(stdout, NULL);
    scanf("%d\n", &T);
    for (int test_case = 1; test_case <= T; test_case++)
    {
        char input[11];
        scanf("%s", input);
        int cnt[26] = { 0, };
        int len = strlen(input);
        int answer = 0;
        for (int i = 0; i < len; i++)
            cnt[input[i] - 'a']++;
 
        for (int i = 0; i < 26; i++)
            answer += (cnt[i] * (cnt[i] + 1) / 2);
        printf("#%d %d\n", test_case, answer);
    }
}