코딩테스트/백준

백준 1802 - 종이접기

수박 서리 2022. 11. 15. 20:49

 

0️⃣ 문제링크

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

 

1802번: 종이 접기

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1

www.acmicpc.net

1️⃣  문제 풀이

가운데를 기준으로 양쪽이 비대칭을 이루는지 알아내는 문제이다.

예) 0100101 4번째 기준으로

     010 0 101 으로 나뉨

그리고 왼쪽 010 오른쪽 101도 대칭인지 확인해야하는데

이미 첫번째에서 양쪽이 대칭인데 비교했기때문에

한쪽만 또 검사해주면됨

게속 이런 식으로 검사를 해주면 된다.

2️⃣ 내 코드

#include <iostream>
#include <string>

using namespace std;
bool check(string input, int startIdx, int endIdx)
{

    if (startIdx >= endIdx)
    {

    return true;
    }
    int left = startIdx;
    int right = endIdx;

    while (left < right)
    {

        if (input[left++] == input[right--])
        {
            return false;
        }
    }
    return check(input, startIdx, right - 1);
}
   
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
        int T;
        cin >> T;

    for (int t = 0; t < T; t++)
    {
        string input;
        cin >> input;

        if (input.length() % 2 == 0)
        {
            cout << "NO\n";
            continue;
        }
 
        bool b = check(input, 0, input.length() - 1);
        
        if(b)
             cout << "YES\n";
        else
             cout << "NO\n";
        
        
    }
    return 0;
}