[백준 1802번] 종이 접기 (C++)

문제링크 : https://www.acmicpc.net/problem/1802

1802번: 종이 접기

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


bool check(string s, int start, int end)
{
    if(start >= end)  //같은 값이 없다면
    {
        return true;
    }

    int l = start;
    int r = end;

    while(l < r)
    {
        if(s[l++] == s[r--])  //중앙을 기준으로 좌우 값이 같다면
        {
            return false;
        }
    }
    return check(s, start, r-1);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   
    int T;
    string paper;
    cin >> T;
    while(T--)
    {
        cin >> paper;
        if(paper.length() % 2 == 0)  //짝수 인경우는 전부 불가능
        {
            cout << "NO\n";
            continue; 
        }

        if(check(paper, 0, paper.length()-1) == true)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }

    return 0;
}

짝수일 때는 불가능하고 홀수일때만 가능하다.

홀수일 때, 중앙값을 기준으로 그 좌우 값은 서로 달라야 한다.