[백준/분할정복/C++] 1992번 쿼드트리

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

1992번: 쿼드트리

문제가 처음에는 이해가 안됐는데 아래처럼 풀면 된다

분할정복을 사용하면 된다

#include <bits/stdc++.h>

using namespace std;

int n;
string mapp[64];

bool check(int x, int y, int n){

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(mapp[x+i][y+j] != mapp[x][y])
                return false;
        }
    }
    return true;
}

void divide(int x, int y, int n){
    if(check(x,y,n)){
        cout << mapp[x][y];
        return;
    }
    int div = n/2;
    cout << '(';
    for(int i=0; i<2; i++){
        for(int j=0; j<2; j++){
            divide(x+div*i, y+div*j, div);
        }
    }
    cout << ')';
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for(int i=0; i<n; i++){
        cin >> mapp[i];
    }

    divide(0, 0, n);

    return 0;
}

비슷한 문제

https://develop-me-z.tistory.com/126

[백준/분할정복/C++] 1780번 종이의 개수