1802-종이접기(브론즈1)

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

1802번: 종이 접기

문제풀이) 이 문제를 살펴 보면 정 가운데를 접고 있기 때문에 가운데를 기준으로 양쪽은 반드시 거꾸로 된 모습이다.

가령 가운데 0 이고 오른쪽이 01 이 되었다면 왼쪽은 01 과 같이 01001 과 같이 되어야 한다. 즉 01010 과 같이 왼쪽과 오른쪽의 위치(0번째 위치와 4번째 위치가 동일하고 1번째 위치와 3번째 위치가 동일한 결과가 나올 수가 없다.) 가 같으면 만들 수가 없는 것이다.

하지만 0000111 처럼 되는 경우에는 가운데 0 을 기준으로 왼쪽 000, 오른쪽 111 이 되었다고 해도 왼쪽 000 역시 가운데 0 을 기준으로 양옆이 서로 달라야 하는데 이러한 부분을 체크해 주면 된다.

#include <iostream>
#include <cstring>

using namespace std;

bool check(char paper[],int s,int e)
{
    if(s>=e) return true;
    int l = s;
    int r = e;
    while(l<r)
    {
        if(paper[l]==paper[r]) return false;
        l++;
        r--;
    }
    return check(paper,s,r-1);
}

int main()
{
    char paper[3010];
    int t;
    cin >> t;
    while(t--)
    {
        cin >> paper;
        int len = strlen(paper);
        if(len%2==0) cout << "NO" << endl;
        else if(check(paper,0,len-1)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}