백준 23304 (C++) 아카라카

 

아이디어

재귀를 연습하기에 좋은 문제였다.

재귀의 base case는 길이가 1일때이다. (길이가 1일때는 팰린드롬이다.)

 

길이가 2 이상인 경우는, 문자열을 반으로 나눈다.

길이가 짝수인 경우, 반으로 그대로 나누고, 홀수인 경우는 가운데 문자를 기준으로 반으로 나눈다.

이때 반으로 나눈 문자열 다르다면 바로 "아카라카"의 조건에서 탈락이다.

 

반으로 나눈 그 문자열을 다시 재귀함수의 인자로 넣음으로서 

해당 문자열 또한 "아카라카"인지 검사한다.

 

반으로 나눈 기준 앞 뒤의 문자열이 모두 아카라카라면 

합친 문자열 또한 아카라카이다.

 

 

 

 

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

23304번: 아카라카

 

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

bool isAka(string s) {
    int len = s.length();
    if (len == 1) {
        return true;
    }
    string l = s.substr(0, len / 2);
    string r = s.substr((len + 1) / 2, len);
    if (l != r) {
        return false;
    }
    if (isAka(l) && isAka(r)) {
        return true;
    }
    return false;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string str;
    cin >> str;
    if (isAka(str)) {
        cout << "AKARAKA";
    }
    else cout << "IPSELENTI";
    return 0;
}