[BOJ/백준][Silver1] 17609 : 회문 (C++)

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

17609번: 회문

 

 

[난이도] Silver1
[유형] 재귀

[풀이]
sol(int l,int r,bool use)
l : 좌측 index,
r :오른쪽 index,
use : 문자 1개를 제거하는 연산을 사용할 수 있는 상태인지

위의 재귀함수를 만들어서,
s[l]!=s[r]인 상태가 왔을 때, 제거하는 연산 (use)를 사용해준 뒤 재귀호출을 한번 더 해준 뒤
그 결과를 출력해주면 됩니다.

 

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
string s;
int tc;
int sol(int l,int r,bool use){
    while(l<=r){
        if(s[l]==s[r]) {
            l++,r--;
            continue;
        }
        if(!use) return 2;
        int ret=2;
        if(s[l+1]==s[r]) {
            ret=sol(l+1,r,0);
            if(ret!=2) return 1;
        }
        if(s[l]==s[r-1]) {
            ret=sol(l,r-1,0); 
            if(ret!=2) return 1;
        }
        return ret;
    }
    return 0;
}
int main(){
    cin >> tc;
    while(tc--){
        cin >> s;
        printf("%d\n",sol(0,s.size()-1,1));
    } 
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/17609.cpp