[C++][백준 23304] 아카라카

문제

접근 방법

함정을 파악하는 게 중요하다.

접두사와 접미사가 아카라카 팰린드롬이어야 한다는 것은 접두사와 접두사의 접두사와 접미사도 아카라카 팰린드롬이어야 한다는 재귀적인 구조를 가진다.

코드

#include <iostream>
using namespace std;
string S;
bool isPalindrome(int start, int end)
{
    int len = end - start;
    int halfLen = len / 2;

    if (len == 1)
    {
        return true;
    }

    for (int i = 0; i < halfLen; ++i)
    {
        if (S[start + i] != S[end - i - 1])
        {
            return false;
        }
    }

    return isPalindrome(start, start + halfLen) && isPalindrome(end - halfLen, end);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> S;

    cout << (isPalindrome(0, S.size()) ? "AKARAKA" : "IPSELENTI");

    return 0;
}

풀이

재귀 함수로 절반을 나누면서 팰린드롬인지 확인해 주면 된다.