[백준 17609번] 회문 (C++)

문제링크 : https://www.acmicpc.net/problem/17609

17609번: 회문

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int T;
string s;

int func(int left, int right, int check)
{
    while(left<right)
    {
        if(s[left] == s[right]) //회문
        {
            left++;
            right--;
        }
        else
        {
            if(check == 0) //시간초과대비 유사회문 체크
            {
                if(func(left+1, right, 1) == 0 || func(left, right-1, 1) == 0)  //유사회문
                {
                    return 1;
                }
                else
                {
                    return 2;
                }
            }
            else //전부 불가
            {
                return 2;
            }
        }
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> T;

    while(T--)
    {
        cin >> s;

        cout << func(0, s.size()-1, 0) << "\n";
    }

    return 0;

}

시작과 마지막에 있는 문자를 비교해가면서 틀릴 경우에는 유사회문이 가능한지 아닌지를 판별한다.

판별해야할 문자열이 mmu라고 가정하면, 앞에 m을 제거하고 뒤에 mu가 같은지, 뒤에 u를 제거하고 앞에 mm이 같은지를 체크한다.

 

이때 유사회문 체크를 반복하지 않도록 체크 변수를 두고 했으면 1로 표시하여 중복을 방지한다.

이를 안하면 시간초과가 발생한다.