[알고리즘 문제] algospot - PICNIC

https://algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

입력으로 문자열의 길이가 1,000 원본 그림의 크기는 2^20 x 2^20이기 때문에 압축된 문자열을 분할하여 배열에 체크하려고 하면 그 값이 너무 커지게 됩니다. 그렇기 때문에 압축된 문자열을 사용해서 바로 상/하를 뒤집는 방법을 생각해야 합니다.

 

그림은 4분면으로 구성되고 x를 기준으로 해당 분면에서 작은 4분면으로 다시 분할합니다. 문제는 이 4분면을 상/하로 뒤집는 것입니다.

그렇기 때문에

 

1사분면은 상/하 뒤집힌 채로 3사분면

2사분면은 상/하 뒤집힌 채로 4사분면

 

으로 이동하게 됩니다. 

 

문제는 분할정복 기법을 사용하였고, 재귀함수에서 기저조건은 해당 iterator값이 'b'이거나 'w'인 값이 됩니다.

#include <iostream>
#include <string>

using namespace std;

string reverse(string::iterator &it)
{
    char head = *it;
    ++it;
    if (head == 'b' || head == 'w')
    {
        return string(1, head);
    }

    string upperLeft = reverse(it);
    string upperRight = reverse(it);
    string lowerLeft = reverse(it);
    string lowerRight = reverse(it);

    return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}
int main()
{

    int T;
    cin >> T;
    string s;
    while (T--)
    {

        cin >> s;
        string::iterator it = s.begin();
        cout << reverse(it) << "\n";
    }
    return 0;
}