[BOJ/CPP] 아카라카 - 23304번 / C++ 풀이

 

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

23304번: 아카라카

 

팰린드롬 판정 문제이다.

재귀를 사용하여 문자열을 계속 반으로 나누고 길이가 1이 될 때까지 혹은 팰린드롬이 아닐 때까지 판정하면 된다.

일반적인 팰린드롬이랑은 다르게 반으로 나눈 문자열도 팰린드롬인지 확인해야한다.

 

짝수일 경우

aaabbaaa -> 처음

aaab baaa -> 나누어짐

aa ab ba aa -> 또 나누어짐

a a a b b a a a -> 또 나누어짐

 

홀수일 경우

acabaca -> 처음

aca aca -> b는 빼고 나누어짐

a a a a-> c는 빼고 나누어짐

 

abba의 경우는 아카라카 팰린드롬이 아님

 

#include <bits/stdc++.h>
using namespace std;

bool ans = true;

void IsPalin(string& s, int start, int end, int recurSize) {
	// 길이가 1까지 줄어들었다면 return
	if (recurSize == 1) {
		return;
	}

	for (int i = start, j = end - 1; i < recurSize / 2; i++, j--) {
		// 앞 뒤가 같지 않다면 팰린드롬이 아님
		if (s[i] != s[j]) {
			ans = false;
			return;
		}
	}

	// 이 문자열이 짝수라면
	if (int(s.length()) % 2 == 0) {
		// 문자열 반을 잘라서 재귀를 돌릴 것임
		// 왼쪽
		IsPalin(s, start, end / 2, recurSize / 2);
		// 오른쪽
		IsPalin(s, end / 2, end, recurSize / 2);
	}
	// 홀수일 경우
	else {
		IsPalin(s, start, end / 2, recurSize / 2);
        // 가운데 문자열은 제외하고 넘겨줌
		IsPalin(s, end / 2 + 1, end, recurSize / 2);
	}
}

int main() {
	string s; cin >> s;

	IsPalin(s, 0, s.length(), s.length());

	if (ans) {
		cout << "AKARAKA";
	}
	else {
		cout << "IPSELENTI";
	}
}