[KOI 2019 1차대회][초등부2번] 회문

문제:

https://www.acmicpc.net/problem/17609

17609번: 회문

 

문제해석:

회문(回文) 또는 팰린드롬(palindrome)은 앞에서 읽으나 거꾸로 읽으나 같은 문장을 뜻한다

ex) level, 다시합시다

 

이 문제의 특징은 회문은 아니지만 한 글자를 삭제하면 회문이되는 "유사회문" 이라는 상태가있다는 것이다.

따라서 입력으로 주어진 문자열은 총 3가지 상태로 표현할수있다.

0 : 회문

1 : 유사회문

2 : 회문X 유사회문X

 

각 상태를 나타내는 숫자의 특징은 회문을 만들기 위해 삭제해야할 글자의 갯수라 볼수있다.

회문과 유사회문은 삭제해야할 글자수가 각각 0개, 1개가 자명하지만

회문과 유사회문이 아닌 문자열은 삭제해야할 글자수가 2개인 순간부터 삭제해야할 글자수를 찾는것이

무의미하다.

 

결국 이문제의 핵심은 "회문을 만들기 위해 삭제해아할 글자수" 이다.

위 그림속의 문자열은 "twpoxopiwt" 총 10글자이며 7번째 문자를 삭제하면 유사회문이 된다.

 

재귀함수를 통해 입력된 문자열의 상태를 파악을 해볼것인데 매개변수로 어떤것들이 필요할까?

현재 가르키는 왼쪽문자 인덱스(위치), 오른쪽 문자 인덱스, 세번째로는 지금까지 삭제한 문자갯수이다!

함수원형: int solve(int left, int right, int cnt) // 문자열 상태(0 or 1 or 2)를 반환할 것이니 반환자료형은 int이다.

 

자 그럼 재귀함수임으로 당연히 기저사례(base-case)가 존재한다 문자열의 길이 홀수일경우 left == right,

짝수일경우 left>right 즉, 엇갈릴 경우 모든 문자검사가 끝났다는것이다. 또한 삭제한 문자가 2개 이상인 경우는

회문과 유사회문이 아님으로 더이상 재귀호출할 필요없이 현재 삭제한 문자갯수를 반환한다.

 

기저사례에서 반환이 안됬다는 것은 호출을 통한 검사가 필요하다는 것인데 위 그림의 두 노랑색 인덱스를 보자.

저 상태로 부터 2가지 상태가 발생한다. 첫 번째로는 2번(left)문자를 삭제하는 것이고 두 번째로는 7번(right)문자를 삭제하는 것이다. 자 그러면 두상태로부터 얻은 결과값중 최소값을 선택하면 된다!

2번(left)문자를 삭제한경우 2(회문X, 유사회문X)가 반환이 되고 7번(right)문자를 삭제한경우 1(유사회문)이 반환이 되는데 이 상황에선 우리는 유사회문 되는경우를 가져오기위해 최소값을 반환한다.

 

코드:

#include<bits/stdc++.h>
 
using namespace std;
 
const int MAX_N = 1e5+5;
char str[MAX_N];
int solve(int left, int right, int cnt)
{
    if(left>=right || cnt>=2) return cnt; // base-case
    if(str[left] == str[right]) return solve(left+1,right-1,cnt);
    else{
        return min(solve(left+1,right,cnt+1),solve(left,right-1,cnt+1));
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    int TC;
    
    cin >> TC; //test case
    while(TC--){
        cin >> str;
        cout << solve(0,strlen(str)-1, 0) << '\n';       
    }
    return 0;
}