백준 1802번 종이 접기 C++

출처 : https://www.acmicpc.net/problem/1802

 

종이의 중간지점을 정해서 접었을 때 대칭되는 점들이 모두 다르다면 동호의 규칙대로 접을 수 있는 것이다.

종이가 전부 접힐 때까지 분할 정복을 통해 해결할 수 있다. 

그리고 문자열의 길이가 항상 2^n - 1이라고 했기 때문에 길이가 짝수가 되는 경우는 고려하지 않아도 된다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

bool isAns = true;
string str;

void rec(int idx, int n) {
	if (n == 0) return;
	for (int i = 1; i <= n; i++) {
		if (str[idx + i] == str[idx - i]) {
			isAns = false;
			return;
		}
	}
	rec(idx / 2, n / 2);
}

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

	int t;
	cin >> t;
	while (t--) {
		cin >> str;
		rec(str.length() / 2, str.length() / 2);
		if (isAns) cout << "YES" << "\n";
		else cout << "NO" << "\n";
		isAns = true;
	}
};